#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 = 2;
const int T = N / K + 5;
int n, l;
int a[N], gr[N], nxt[N], need[N], group[T];
set < ii > s[T], all;
void rebuild(int i) {
group[i] = -1;
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;
gr[id] = i;
int next = all.lower_bound(ii(x + l + 1, 0)) -> second;
//printf("id = %d next = %d\n", id, next);
if(a[next] <= last) {
need[id] = need[next] + 1;
nxt[id] = nxt[next];
}
else {
need[id] = 1;
nxt[id] = next;
}
}
}
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);
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]);
}
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 update(int i, int x) {
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));
int aft = all.lower_bound(ii(a[i] + 1, 0)) -> second;
for(int j = ind - 1; j >= 0; j--) {
if(s[j].size()) {
int st = s[j].begin() -> second;
if(a[st] + l >= a[aft]) {
group[j] = i;
}
else {
rebuild(j);
break;
}
}
}
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);
for(int j = ind - 1; j >= 0; j--) {
if(s[j].size()) {
int st = s[j].begin() -> second;
if(a[st] + l >= a[i]) {
group[j] = i;
}
else {
rebuild(j);
break;
}
}
}
int pos = all.begin() -> second, ans = 0;
while(pos < n) {
if(group[gr[pos]] != -1) {
ans++;
pos = group[gr[pos]];
}
else {
ans += need[pos];
pos = nxt[pos];
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
24676 KB |
Output is correct |
2 |
Correct |
0 ms |
24676 KB |
Output is correct |
3 |
Correct |
4 ms |
24676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
24676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
28 ms |
25732 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
9000 ms |
26256 KB |
Program timed out |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
144 ms |
38668 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |