#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int U = 1500; // 400 ~ 1500
const int B = 1500; // 400 ~ 1500
struct elem{
int val;
int next;
int cnt;
};
bool operator<(elem a, elem b){ return a.val < b.val; }
vector<elem> bucket[105];
int sentinel;
int b[150005];
int a[150005], n, l;
int q_cnt;
void make_arr(){
int piv = 0;
for (int i=0; i<sentinel; i++) {
for (int j=0; j<bucket[i].size(); j++) {
a[piv++] = bucket[i][j].val;
}
}
}
void bucket_clear(){
for (int i=0; i<sentinel; i++) {
bucket[i].clear();
int piv = min(n-i*B,B);
int pt = piv;
bucket[i].resize(piv);
for (int j=i*B+piv-1; j>=i*B; j--) {
while (pt && b[i*B+pt-1] > b[j] + l) pt--;
if(pt == piv){
bucket[i][j-i*B] = (elem){b[j],-1,0};
}
else{
bucket[i][j-i*B].val = b[j];
if(bucket[i][pt-i*B].next == -1){
bucket[i][j-i*B].next = pt-i*B;
}
else{
bucket[i][j-i*B].next = bucket[i][pt-i*B].next;
}
bucket[i][j-i*B].cnt = bucket[i][pt-i*B].cnt + 1;
}
}
}
}
void single_bucket_update(int buck_num, int pos, int val){
}
int query(){
int pos = 0, ret = 0;
for (int i=0; i<sentinel; ) {
if(bucket[i].empty()){
i++;
continue;
}
ret += bucket[i][pos].cnt + 1;
if(bucket[i][pos].next != -1) pos = bucket[i][pos].next;
int new_buck = i+1;
int new_pos = bucket[i][pos].val + l;
while (1){
if(new_buck == sentinel) break;
if(lower_bound(bucket[new_buck].begin(),bucket[new_buck].end(),(elem){new_pos+1,0,0})
!= bucket[new_buck].end()) break;
new_buck++;
}
if(new_buck == sentinel) break;
i = new_buck;
pos = (int)(lower_bound(bucket[new_buck].begin(),bucket[new_buck].end(),(elem){new_pos+1,0,0}) - bucket[new_buck].begin());
}
return ret;
}
void init(int N, int L, int* X){
memcpy(a,X,sizeof(int) * N);
n = N;
l = L;
while (sentinel * B < n) sentinel++;
bucket_clear();
}
int update(int i, int y){
q_cnt = (q_cnt + 1) % U;
/*
int piv = i;
int pos = -1;
for (int i=0; i*B<n; i++) {
if(piv >= bucket[i].size()){
piv -= bucket[i].size();
}
else{
pos = i;
break;
}
}
single_bucket_update(pos,piv,y);*/
if(1 || q_cnt == 0){
// make_arr();
a[i] = y;
for (int i=0; i<n; i++) {
b[i] = a[i];
}
sort(b,b+n);
bucket_clear();
}
return query();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
18380 KB |
Output is correct |
2 |
Correct |
0 ms |
18380 KB |
Output is correct |
3 |
Correct |
0 ms |
18380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
18380 KB |
Output is correct |
2 |
Correct |
0 ms |
18380 KB |
Output is correct |
3 |
Correct |
0 ms |
18380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
18520 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
18520 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
86 ms |
20064 KB |
SIGSEGV Segmentation fault |
2 |
Halted |
0 ms |
0 KB |
- |