#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
#define ull unsigned long long
const int mxn = 150000, sq = 400;
int n, qq = 0, l;
int x[mxn + 1], mx[mxn + 1], cnt[mxn + 1], block[mxn + 1];
vt<pii>comp[mxn + 1];
void build(int s){
int r = sz(comp[s]);
for(int i = sz(comp[s]) - 1; i >= 0; i--){
while(r > 0 && comp[s][i].fi + l < comp[s][r - 1].fi)r--;
if(r == sz(comp[s])){
cnt[comp[s][i].se] = 1; mx[comp[s][i].se] = comp[s][i].fi + l;
}else{
cnt[comp[s][i].se] = cnt[comp[s][r].se] + 1; mx[comp[s][i].se] = mx[comp[s][r].se];
}
}
}
void solve(){
for(int i = 0; i < n; i++){
block[i] = i / sq;
comp[i / sq].pb(mpp(x[i], i));
}
for(int i = 0; i <= (n - 1) / sq; i++)build(i);
}
void init(int N, int L, int X[])
{
n = N; l = L;
for(int i = 0; i < n; i++)x[i] = X[i];
solve();
}
int getblock(int x){
for(int i = (n - 1) / sq; i >= 0; i--){
if(sz(comp[i]) == 0)continue;
if(comp[i][0].fi <= x)return(i);
}
return(0);
}
void rebuild(){
vt<pii>all;
for(int i = 0; i <= (n - 1) / sq; i++){
for(auto j: comp[i])all.pb(j);
comp[i].clear();
}
for(int i = 0; i <= n - 1; i++){
block[all[i].se] = i / sq;
comp[i / sq].pb(all[i]);
}
for(int i = 0; i <= (n - 1) / sq; i++)build(i);
}
int update(int id, int y)
{
int bl = block[id];
for(int i = 0; i < sz(comp[bl]); i++){
if(comp[bl][i].se == id){
comp[bl].erase(comp[bl].begin() + i);
break;
}
}
build(bl);
x[id] = y;
int br = getblock(x[id]), pos = sz(comp[br]); block[id] = br;
for(int i = 0; i < sz(comp[br]); i++){
if(comp[br][i].fi > y){
pos = i;
break;
}
}
comp[br].insert(comp[br].begin() + pos, mpp(x[id], id));
build(br);
int position = -1, camera = 0;
for(int i = 0; i <= (n - 1) / sq; i++){
if(sz(comp[i]) == 0)continue;
int id = lower_bound(ALL(comp[i]), mpp(position + 1, -1)) - comp[i].begin();
if(id == sz(comp[i]))continue;
else{
camera += cnt[comp[i][id].se]; position = mx[comp[i][id].se];
}
}
++qq;
if(qq == sq){
rebuild(); qq = 0;
}
return(camera);
}
/*
#define MAX_N 1000000
#define MAX_M 1000000
static int N,L,M;
static int X[MAX_N];
static int ii[MAX_M];
static int yy[MAX_M];
static int sol[MAX_M];
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(3==scanf("%d %d %d",&N,&L,&M));
for(i=0; i<N; i++)
my_assert(1==scanf("%d",&X[i]));
for(i=0; i<M; i++)
my_assert(3==scanf("%d %d %d",&ii[i],&yy[i],&sol[i]));
}
int main()
{
int i, ans;
read_input();
init(N,L,X);
for(i=0; i<M; i++) {
ans = update(ii[i],yy[i]);
cout << ans << "\n";
}
printf("Correct.\n");
return 0;
}
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
12888 KB |
Output is correct |
2 |
Correct |
2 ms |
12892 KB |
Output is correct |
3 |
Correct |
3 ms |
12892 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
12888 KB |
Output is correct |
2 |
Correct |
2 ms |
12892 KB |
Output is correct |
3 |
Correct |
3 ms |
12892 KB |
Output is correct |
4 |
Correct |
3 ms |
12892 KB |
Output is correct |
5 |
Correct |
2 ms |
12892 KB |
Output is correct |
6 |
Correct |
2 ms |
12892 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
12888 KB |
Output is correct |
2 |
Correct |
2 ms |
12892 KB |
Output is correct |
3 |
Correct |
3 ms |
12892 KB |
Output is correct |
4 |
Correct |
3 ms |
12892 KB |
Output is correct |
5 |
Correct |
2 ms |
12892 KB |
Output is correct |
6 |
Correct |
2 ms |
12892 KB |
Output is correct |
7 |
Correct |
196 ms |
14304 KB |
Output is correct |
8 |
Correct |
217 ms |
14572 KB |
Output is correct |
9 |
Correct |
275 ms |
15884 KB |
Output is correct |
10 |
Correct |
277 ms |
15696 KB |
Output is correct |
11 |
Correct |
269 ms |
15440 KB |
Output is correct |
12 |
Correct |
474 ms |
16272 KB |
Output is correct |
13 |
Correct |
289 ms |
15500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
12888 KB |
Output is correct |
2 |
Correct |
2 ms |
12892 KB |
Output is correct |
3 |
Correct |
3 ms |
12892 KB |
Output is correct |
4 |
Correct |
3 ms |
12892 KB |
Output is correct |
5 |
Correct |
2 ms |
12892 KB |
Output is correct |
6 |
Correct |
2 ms |
12892 KB |
Output is correct |
7 |
Correct |
196 ms |
14304 KB |
Output is correct |
8 |
Correct |
217 ms |
14572 KB |
Output is correct |
9 |
Correct |
275 ms |
15884 KB |
Output is correct |
10 |
Correct |
277 ms |
15696 KB |
Output is correct |
11 |
Correct |
269 ms |
15440 KB |
Output is correct |
12 |
Correct |
474 ms |
16272 KB |
Output is correct |
13 |
Correct |
289 ms |
15500 KB |
Output is correct |
14 |
Correct |
266 ms |
15172 KB |
Output is correct |
15 |
Correct |
335 ms |
14996 KB |
Output is correct |
16 |
Correct |
774 ms |
16336 KB |
Output is correct |
17 |
Correct |
839 ms |
17236 KB |
Output is correct |
18 |
Correct |
918 ms |
17328 KB |
Output is correct |
19 |
Correct |
571 ms |
17436 KB |
Output is correct |
20 |
Correct |
853 ms |
17316 KB |
Output is correct |
21 |
Correct |
799 ms |
17212 KB |
Output is correct |
22 |
Correct |
495 ms |
16816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
12888 KB |
Output is correct |
2 |
Correct |
2 ms |
12892 KB |
Output is correct |
3 |
Correct |
3 ms |
12892 KB |
Output is correct |
4 |
Correct |
3 ms |
12892 KB |
Output is correct |
5 |
Correct |
2 ms |
12892 KB |
Output is correct |
6 |
Correct |
2 ms |
12892 KB |
Output is correct |
7 |
Correct |
196 ms |
14304 KB |
Output is correct |
8 |
Correct |
217 ms |
14572 KB |
Output is correct |
9 |
Correct |
275 ms |
15884 KB |
Output is correct |
10 |
Correct |
277 ms |
15696 KB |
Output is correct |
11 |
Correct |
269 ms |
15440 KB |
Output is correct |
12 |
Correct |
474 ms |
16272 KB |
Output is correct |
13 |
Correct |
289 ms |
15500 KB |
Output is correct |
14 |
Correct |
266 ms |
15172 KB |
Output is correct |
15 |
Correct |
335 ms |
14996 KB |
Output is correct |
16 |
Correct |
774 ms |
16336 KB |
Output is correct |
17 |
Correct |
839 ms |
17236 KB |
Output is correct |
18 |
Correct |
918 ms |
17328 KB |
Output is correct |
19 |
Correct |
571 ms |
17436 KB |
Output is correct |
20 |
Correct |
853 ms |
17316 KB |
Output is correct |
21 |
Correct |
799 ms |
17212 KB |
Output is correct |
22 |
Correct |
495 ms |
16816 KB |
Output is correct |
23 |
Correct |
2434 ms |
25140 KB |
Output is correct |
24 |
Correct |
2507 ms |
25236 KB |
Output is correct |
25 |
Correct |
1788 ms |
25040 KB |
Output is correct |
26 |
Correct |
2213 ms |
25036 KB |
Output is correct |
27 |
Correct |
2312 ms |
24844 KB |
Output is correct |
28 |
Correct |
923 ms |
18048 KB |
Output is correct |
29 |
Correct |
870 ms |
18072 KB |
Output is correct |
30 |
Correct |
900 ms |
18060 KB |
Output is correct |
31 |
Correct |
870 ms |
18256 KB |
Output is correct |
32 |
Correct |
1877 ms |
24480 KB |
Output is correct |
33 |
Correct |
1762 ms |
23844 KB |
Output is correct |
34 |
Correct |
1949 ms |
24612 KB |
Output is correct |
35 |
Correct |
1981 ms |
24808 KB |
Output is correct |
36 |
Correct |
1912 ms |
24572 KB |
Output is correct |
37 |
Correct |
2461 ms |
26900 KB |
Output is correct |
38 |
Correct |
1943 ms |
23612 KB |
Output is correct |
39 |
Correct |
1874 ms |
24476 KB |
Output is correct |
40 |
Correct |
1934 ms |
23744 KB |
Output is correct |
41 |
Correct |
3057 ms |
24580 KB |
Output is correct |
42 |
Correct |
3162 ms |
24672 KB |
Output is correct |