#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;
const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;
const int N = 150000 + 5;
const int K = 400;
const int T = N / K + 5;
int n, l;
int a[N], nxt[N], need[N];
set < ii > s[T], all;
inline int get(int x) {
return all.lower_bound(ii(x + l + 1, 0)) -> second;
}
void rebuild(int i) {
int last = 0;
if(s[i].size())
last = (--s[i].end()) -> first;
for(set < ii > :: reverse_iterator it = s[i].rbegin(); it != s[i].rend(); it++) {
int x = it -> first;
int id = it -> second;
int next = get(x);
//printf("id = %d next = %d\n", id, next);
//printf("id = %d next = %d\n", id, next);
if(a[next] <= last) {
nxt[id] = nxt[next];
need[id] = need[next] + 1;
}
else {
nxt[id] = id;
need[id] = 0;
}
}
}
ii b[N];
void init() {
all.clear();
for(int i = 0; i < n; i++) {
all.insert(ii(a[i], i));
b[i] = ii(a[i], i);
}
a[n] = 2 * inf;
all.insert(ii(2 * inf, n));
sort(b, b + n);
int ind = 0;
for(int i = 0; i * K < n; i++) {
s[i].clear();
for(int j = i * K; j < n and j < (i + 1) * K; j++) {
s[i].insert(b[j]);
}
ind = i;
}
for(int i = ind; i >= 0; i--)
rebuild(i);
}
void init(int N, int L, int X[]) {
n = N;
l = L;
for(int i = 0; i < n; i++) {
a[i] = X[i];
}
init();
}
int upCnt = 0;
int update(int i, int x) {
upCnt++;
if(upCnt == 400) {
upCnt = 0;
a[i] = x;
init();
}
else {
int ind = -1;
for(int j = 0; j * K < n; j++) {
if(s[j].count(ii(a[i], i))) {
ind = j;
break;
}
}
assert(ind != -1);
s[ind].erase(ii(a[i], i));
all.erase(ii(a[i], i));
rebuild(ind);
a[i] = x;
for(int j = 0; j * K < n; j++) {
ind = j;
if(s[j].size() and x <= (--s[j].end()) -> first)
break;
}
all.insert(ii(a[i], i));
s[ind].insert(ii(a[i], i));
rebuild(ind);
}
int pos = all.begin() -> second, ans = 0, cnt = 0;
while(pos < n) {
//printf("pos = %d\n", pos);
//getchar();getchar();
if(nxt[pos] == pos) {
ans++;
pos = get(a[pos]);
}
else {
ans += need[pos];
pos = nxt[pos];
}
cnt++;
}
assert(cnt <= T + T);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
20296 KB |
Output is correct |
2 |
Correct |
0 ms |
20296 KB |
Output is correct |
3 |
Correct |
0 ms |
20296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
20296 KB |
Output is correct |
2 |
Correct |
3 ms |
20296 KB |
Output is correct |
3 |
Correct |
0 ms |
20296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4118 ms |
21484 KB |
Output is correct |
2 |
Correct |
4647 ms |
21880 KB |
Output is correct |
3 |
Execution timed out |
9000 ms |
24916 KB |
Program timed out |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6917 ms |
21880 KB |
Output is correct |
2 |
Correct |
6601 ms |
22408 KB |
Output is correct |
3 |
Execution timed out |
9000 ms |
24912 KB |
Program timed out |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
9000 ms |
34284 KB |
Program timed out |
2 |
Halted |
0 ms |
0 KB |
- |