#include "elephants.h"
/**
* Author: Nicholas Winschel
* Created: 06.06.2023 11:07:24
**/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
int n,l;
const int MAXN=150000;
const int BS=500;
int pos[MAXN],j[MAXN],h[MAXN],ord[MAXN],w[MAXN];
vi buck[MAXN/BS + 5];
int cnt = 0;
int llt(const vi &v, int x) {
if (!sz(v) || pos[v[0]] >= x) return -1;
int l = 0,r=sz(v);
while (r-l>1) {
int m = (l+r)>>1;
if (pos[v[m]] >= x) r=m;
else l=m;
}
return l;
}
void fixbuck(int i) {
if (sz(buck[i])>=2*BS) cnt=2*BS;
// cerr << "fb: " << i << endl;
// for (int x : buck[i]) cerr << x << " ";
// cerr << endl;
if (!sz(buck[i])) return;
j[buck[i][0]]=pos[buck[i][0]]-l,h[buck[i][0]]=1;
int lp = 0;
for (int k = 1; k < sz(buck[i]); k++) {
while (lp < sz(buck[i])-1 && pos[buck[i][lp+1]]<pos[buck[i][k]]-l) lp++;
if (pos[buck[i][lp]] < pos[buck[i][k]]-l) {
// cerr << "test" << endl;
j[buck[i][k]]=j[buck[i][lp]];
h[buck[i][k]]=h[buck[i][lp]]+1;
} else {
j[buck[i][k]]=pos[buck[i][k]]-l;
h[buck[i][k]]=1;
}
}
}
void fixall() {
// cerr << "REALLOC" << endl;
int cur = 0;
for (int i = 0; i <= (n-1)/BS; i++) {
for (int x : buck[i]) ord[cur++]=x;
buck[i].resize(BS + 1);
}
int c = 0;
for (int i = 0; i < n; i++) {
buck[i/BS][c++]=ord[i];
w[ord[i]]=i/BS;
if (i == n-1 || (i+1)/BS != i/BS) buck[i/BS].resize(c),c=0,fixbuck(i/BS);
}
}
void init(int N, int L, int X[])
{
n = N;
l = L;
memcpy(pos,X,N*sizeof(int));
for (int i = 0; i < N; i++) {
buck[i/BS].push_back(i);
}
fixall();
}
int update(int i, int y)
{
// cerr << "mov: " << i << " " << y << endl;
if (cnt > BS) fixall(),cnt=0;
buck[w[i]].erase(find(buck[w[i]].begin(),buck[w[i]].end(),i));
fixbuck(w[i]);
pos[i]=y;
w[i]=0;
for (int k = 0; k <= (n-1)/BS; k++) {
if (sz(buck[k]) && pos[buck[k][0]] < pos[i]) w[i]=k;
}
int ind = llt(buck[w[i]],pos[i])+1;
buck[w[i]].insert(buck[w[i]].begin()+ind,i);
fixbuck(w[i]);
// for (int i = 0; i < n; i++) {
// cerr << "dbg: " << i << " " << pos[i] << " " << j[i] << " " << h[i] << endl;
// }
int cur = 2e9,ret=0;
for (int i = (n-1)/BS; i >= 0; i--) {
int ind = llt(buck[i],cur);
if (ind >= 0) {
ind=buck[i][ind];
cur=j[ind],ret += h[ind];
// cerr << "jmp: " << cur << " " << ret << endl;
}
}
return ret;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
320 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
320 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
648 ms |
1420 KB |
Output is correct |
8 |
Correct |
688 ms |
1552 KB |
Output is correct |
9 |
Correct |
740 ms |
2456 KB |
Output is correct |
10 |
Correct |
826 ms |
2448 KB |
Output is correct |
11 |
Correct |
694 ms |
2452 KB |
Output is correct |
12 |
Correct |
1182 ms |
2516 KB |
Output is correct |
13 |
Correct |
832 ms |
2456 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
320 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
648 ms |
1420 KB |
Output is correct |
8 |
Correct |
688 ms |
1552 KB |
Output is correct |
9 |
Correct |
740 ms |
2456 KB |
Output is correct |
10 |
Correct |
826 ms |
2448 KB |
Output is correct |
11 |
Correct |
694 ms |
2452 KB |
Output is correct |
12 |
Correct |
1182 ms |
2516 KB |
Output is correct |
13 |
Correct |
832 ms |
2456 KB |
Output is correct |
14 |
Correct |
662 ms |
2060 KB |
Output is correct |
15 |
Correct |
1058 ms |
2148 KB |
Output is correct |
16 |
Correct |
1752 ms |
2952 KB |
Output is correct |
17 |
Correct |
1991 ms |
3668 KB |
Output is correct |
18 |
Correct |
2170 ms |
3300 KB |
Output is correct |
19 |
Correct |
1388 ms |
3252 KB |
Output is correct |
20 |
Correct |
2081 ms |
3660 KB |
Output is correct |
21 |
Correct |
1982 ms |
3352 KB |
Output is correct |
22 |
Correct |
1421 ms |
3240 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
320 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
648 ms |
1420 KB |
Output is correct |
8 |
Correct |
688 ms |
1552 KB |
Output is correct |
9 |
Correct |
740 ms |
2456 KB |
Output is correct |
10 |
Correct |
826 ms |
2448 KB |
Output is correct |
11 |
Correct |
694 ms |
2452 KB |
Output is correct |
12 |
Correct |
1182 ms |
2516 KB |
Output is correct |
13 |
Correct |
832 ms |
2456 KB |
Output is correct |
14 |
Correct |
662 ms |
2060 KB |
Output is correct |
15 |
Correct |
1058 ms |
2148 KB |
Output is correct |
16 |
Correct |
1752 ms |
2952 KB |
Output is correct |
17 |
Correct |
1991 ms |
3668 KB |
Output is correct |
18 |
Correct |
2170 ms |
3300 KB |
Output is correct |
19 |
Correct |
1388 ms |
3252 KB |
Output is correct |
20 |
Correct |
2081 ms |
3660 KB |
Output is correct |
21 |
Correct |
1982 ms |
3352 KB |
Output is correct |
22 |
Correct |
1421 ms |
3240 KB |
Output is correct |
23 |
Correct |
5757 ms |
6412 KB |
Output is correct |
24 |
Correct |
5965 ms |
6440 KB |
Output is correct |
25 |
Correct |
5627 ms |
6204 KB |
Output is correct |
26 |
Correct |
6858 ms |
6216 KB |
Output is correct |
27 |
Correct |
6740 ms |
6216 KB |
Output is correct |
28 |
Correct |
2582 ms |
2248 KB |
Output is correct |
29 |
Correct |
2489 ms |
2252 KB |
Output is correct |
30 |
Correct |
2563 ms |
2372 KB |
Output is correct |
31 |
Correct |
2477 ms |
2248 KB |
Output is correct |
32 |
Correct |
4645 ms |
6220 KB |
Output is correct |
33 |
Correct |
3594 ms |
6272 KB |
Output is correct |
34 |
Correct |
6091 ms |
6208 KB |
Output is correct |
35 |
Correct |
3769 ms |
6708 KB |
Output is correct |
36 |
Correct |
2227 ms |
6208 KB |
Output is correct |
37 |
Correct |
8559 ms |
6756 KB |
Output is correct |
38 |
Correct |
6635 ms |
9872 KB |
Output is correct |
39 |
Correct |
6646 ms |
10908 KB |
Output is correct |
40 |
Correct |
6622 ms |
9904 KB |
Output is correct |
41 |
Execution timed out |
9010 ms |
11264 KB |
Time limit exceeded |
42 |
Halted |
0 ms |
0 KB |
- |