交了两次，第二次比第一次多10分，原来TLE的测试点变成了1000MS……

这说明时限是1s啊，这个题1s过太困难啦

请管理员大人关注一下这个问题

应该是吧2S吧

这题我过了饿……等等我再提交次看看

状态: Accepted

测评机： Xeost[5]

得分： 100分

提交日期： 2010-9-8 17:37:00

有效耗时： 3875毫秒

测试结果1: 通过本测试点|有效耗时62ms

测试结果2: 通过本测试点|有效耗时94ms

测试结果3: 通过本测试点|有效耗时172ms

测试结果4: 通过本测试点|有效耗时1016ms

测试结果5: 通过本测试点|有效耗时46ms

测试结果6: 通过本测试点|有效耗时766ms

测试结果7: 通过本测试点|有效耗时156ms

测试结果8: 通过本测试点|有效耗时188ms

测试结果9: 通过本测试点|有效耗时375ms

测试结果10: 通过本测试点|有效耗时1000ms

好像又改回1s了

……同样的代码，这次竟然第四个点TLE了 囧啊

mb

不用STL竟然也超时

这机子牛啊。。。。。。。。 -_-

// 鄙人又慢又长的代码

#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

#include <algorithm>

#include <iostream>

#include <queue>

using namespace std;

#define MAX_N 510000

#define MAX_M 1210000

#define lgN 20

typedef int nint[MAX_N];

typedef int mint[MAX_M];

typedef int lgnint[lgN];

struct node { int s, p; };

bool operator < (node a, node b) { return a.s < b.s; }

struct Heap

{

mint id, l, r, t;

node v[MAX_M];

int tot, tp;

void push(int _id, int _l, int _r, int _s, int _t)

{

tot++, id[tot] = _id, l[tot] = _l, r[tot] = _r, t[tot] = _t;

tp++, v[tp].p = tot, v[tp].s = _s;

push_heap (v + 1, v + tp + 1);

}

void top(int &_id, int &_l, int &_r, int &_s, int &_t)

{

int p = v[1].p;

_id = id[p], _l = l[p], _r = r[p], _s = v[1].s, _t = t[p];

}

void pop(void)

{

pop_heap (v + 1, v + tp + 1);

tp--;

}

};

Heap heap;

lgnint f[MAX_N], g[MAX_N];

nint sum, lgn;

lgnint po;

long long ans;

int n, m, sl, sr;

void Sparse_table(void)

{

lgn[0] = -1;

for (int i = 1, j = 0; i <= n; i++)

{

lgn[i] = lgn[i - 1];

if (po[j] == i) lgn[i]++, j++;

f[i][0] = sum[i], g[i][0] = i;

}

for (int i = 1, p = 2; i <= lgn[sr]; i++, p <<= 1)

{

for (int j = 1; j <= n - p + 1; j++)

{

int mid = j + (p >> 1);

if (f[mid][i - 1] > f[j][i - 1])

f[j][i] = f[mid][i - 1], g[j][i] = g[mid][i - 1];

else f[j][i] = f[j][i - 1], g[j][i] = g[j][i - 1];

}

}

}

int RMQ(int a, int b, int &t)

{

int lgs = lgn[b - a + 1];

if (f[a][lgs] > f[b - po[lgs] + 1][lgs]) { t = g[a][lgs]; return f[a][lgs]; }

else { t = g[b - po[lgs] + 1][lgs]; return f[b - po[lgs] + 1][lgs]; }

}

void init(void)

{

freopen ("piano.in", "r", stdin);

freopen ("piano.out", "w", stdout);

scanf ("%d%d%d%d", &n, &m, &sl, &sr);

po[0] = 1;

for (int i = 1; i < lgN; i++)

po[i] = po[i - 1] << 1;

for (int i = 1; i <= n; i++)

scanf ("%d", sum + i), sum[i] += sum[i - 1];

Sparse_table ();

}

void solve(void)

{

for (int i = 1, l, r, s, t; i <= n; i++)

{

l = i + sl - 1, r = i + sr - 1;

if (l > n) break;

if (r > n) r = n;

s = RMQ (l, r, t) - sum[i - 1];

heap.push (i, l, r, s, t);

}

for (int i = 1; i <= m; i++)

{

int id, l, r, s, t, tt;

heap.top(id, l, r, s, t), heap.pop();

ans += s;

if (l < t)

{

s = RMQ (l, t - 1, tt) - sum[id - 1];

heap.push (id, l, t - 1, s, tt);

}

if (r > t)

{

s = RMQ (t + 1, r, tt) - sum[id - 1];

heap.push (id, t + 1, r, s, tt);

}

}

}

int main(void)

{

init ();

solve ();

cout << ans;

return 0;

}