#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 = 1000;
const int T = N / K + 5;
int n, l;
int a[N], gr[N], nxt[N], need[N];
vector < ii > v[T];
set < ii > all;
inline int get(int x) {
return all.lower_bound(ii(x + l + 1, 0)) -> second;
}
void rebuild(int i) {
int last = 0;
if(v[i].size())
last = v[i].back().first;
int pos = (int) v[i].size() - 1;
for(int j = (int) v[i].size() - 1; j >= 0; j--) {
int x = v[i][j].first;
int id = v[i][j].second;
gr[id] = i;
if(x + l >= last) {
nxt[id] = id;
need[id] = 0;
}
else {
while(pos > j + 1 and x + l < v[i][pos - 1].first)
pos--;
nxt[id] = nxt[v[i][pos].second];
need[id] = need[v[i][pos].second] + 1;
}
}
}
ii b[N];
void init(bool flag = 0) {
if(flag) {
for(int i = 0; i < n; i++)
b[i] = ii(a[i], i);
}
else {
int sz = 0;
for(int i = 0; i * K < n; i++) {
for(int j = 0; j < v[i].size(); j++)
b[sz++] = v[i][j];
}
}
int ind = 0;
for(int i = 0; i * K < n; i++) {
v[i].clear();
for(int j = i * K; j < n and j < (i + 1) * K; j++) {
v[i].push_back(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];
all.insert(ii(a[i], i));
}
a[n] = 2 * inf;
all.insert(ii(2 * inf, n));
init(1);
}
int upCnt = 0;
int update(int i, int x) {
int ind = gr[i];
v[ind].erase(lower_bound(v[ind].begin(), v[ind].end(), 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(v[j].size() and ii(a[i], i) <= v[j].back())
break;
}
all.insert(ii(a[i], i));
v[ind].insert(lower_bound(v[ind].begin(), v[ind].end(), ii(a[i], i)), ii(a[i], i));
rebuild(ind);
upCnt++;
if(upCnt == K) {
upCnt = 0;
init();
}
int pos = all.begin() -> second, ans = 0;
while(pos < n) {
if(nxt[pos] == pos) {
ans++;
pos = get(a[pos]);
}
else {
ans += need[pos];
pos = nxt[pos];
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
20868 KB |
Output is correct |
2 |
Correct |
0 ms |
20868 KB |
Output is correct |
3 |
Correct |
0 ms |
20868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
20868 KB |
Output is correct |
2 |
Correct |
0 ms |
20868 KB |
Output is correct |
3 |
Correct |
0 ms |
20868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
758 ms |
21664 KB |
Output is correct |
2 |
Correct |
787 ms |
21936 KB |
Output is correct |
3 |
Correct |
1127 ms |
23516 KB |
Output is correct |
4 |
Correct |
1040 ms |
23516 KB |
Output is correct |
5 |
Correct |
1142 ms |
23516 KB |
Output is correct |
6 |
Correct |
2354 ms |
23796 KB |
Output is correct |
7 |
Correct |
1346 ms |
23516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1040 ms |
21928 KB |
Output is correct |
2 |
Correct |
1128 ms |
22060 KB |
Output is correct |
3 |
Correct |
2823 ms |
23516 KB |
Output is correct |
4 |
Correct |
3529 ms |
24848 KB |
Output is correct |
5 |
Correct |
3967 ms |
24848 KB |
Output is correct |
6 |
Correct |
2345 ms |
24712 KB |
Output is correct |
7 |
Correct |
3497 ms |
24848 KB |
Output is correct |
8 |
Correct |
4073 ms |
24848 KB |
Output is correct |
9 |
Correct |
2434 ms |
24712 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
9000 ms |
29076 KB |
Program timed out |
2 |
Halted |
0 ms |
0 KB |
- |