#pragma GCC optimize ("Ofast")
#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5+5;
const int x = 400;
#define all(x) x.begin(), x.end()
#define mk make_pair
#define pb push_back
#define f first
#define s second
int n, l, at, group[MAXN], pos[MAXN];
pii dp[MAXN], inter_gp[MAXN]; // qtd de cameras e pos onde termina
set<pii> ele, ele_gp[MAXN];
void init(int N, int L, int X[]) {
n = N;
l = L;
for(int i = 0; i < n; i++)
ele.insert({X[i], i}), pos[i] = X[i];
for(int i = 0; i < n; i++)
group[i] = i/x, ele_gp[i/x].insert({X[i],i});
group[n] = (n-1)/x+1;
for(int i = 0; i <= (n-1)/x; i++)
inter_gp[i] = mk((*ele_gp[i].begin()).f, (*ele_gp[i].rbegin()).f);
for(int i = n-1; i >= 0; i--) {
auto ptr = ele.upper_bound(mk(X[i] + l, 1e9));
if(ptr == ele.end()) { dp[i] = mk(0, i); continue; }
int j = (*ptr).s;
if(group[i] < group[j]) dp[i] = mk(0, i);
else dp[i] = mk(1 + dp[j].f, dp[j].s);
}
}
void att(int G) {
vector<int> ord;
for(auto [v, i] : ele_gp[G])
ord.pb(i);
reverse(all(ord));
for(int j = 0, k = 0; j < ord.size(); j++) {
while(pos[ord[k]] > pos[ord[j]] + l) k++;
if(k == 0) dp[ord[j]] = mk(0, ord[j]);
else dp[ord[j]] = mk(1 + dp[ord[k-1]].f, dp[ord[k-1]].s);
}
}
int update(int i, int y) {
at++;
if(at == x) {
vector<int> ord;
ele.erase({pos[i], i});
ele.insert({y,i});
pos[i] = y;
for(int j = 0; j <= (n-1)/x; j++)
ele_gp[j].clear();
int cnt = 0;
for(auto [v, j] : ele)
group[j] = cnt/x, ord.pb(j), ele_gp[cnt/x].insert({v, j}), cnt++;
for(int j = 0; j <= (n-1)/x; j++)
inter_gp[j] = mk((*ele_gp[j].begin()).f, (*ele_gp[j].rbegin()).f);
reverse(all(ord));
for(int j = 0, k = 0; j < ord.size(); j++) {
while(pos[ord[k]] > pos[ord[j]] + l) k++;
if(k == 0 or group[ord[k-1]] > group[ord[j]]) dp[ord[j]] = mk(0, ord[j]);
else dp[ord[j]] = mk(1 + dp[ord[k-1]].f, dp[ord[k-1]].s);
}
at = 0;
}
else {
int G1 = group[i];
ele.erase({pos[i], i});
ele_gp[G1].erase({pos[i], i});
int ptr = upper_bound(inter_gp, inter_gp+(n-1)/x+1, mk(y,(int)2e9)) - inter_gp;
if(ptr > 0) ptr--;
int G2 = ptr;
group[i] = G2;
pos[i] = y;
ele.insert({y,i});
inter_gp[G2].s = max(inter_gp[G2].s, y);
ele_gp[G2].insert({y, i});
if(G2 < G1) swap(G1, G2);
att(G2);
if(G2 != G1) att(G1);
}
int j = (*ele.begin()).s, r = 0;
while(j < n) {
if(dp[j].f > 0) {
r += dp[j].f;
j = dp[j].s;
}
else {
auto ptr = ele.upper_bound(mk(pos[j] + l, 1e9));
r++;
if(ptr == ele.end()) break;
j = (*ptr).s;
}
}
return r;
}
// g++ elephants.cpp grader.cpp -o elephants
Compilation message
elephants.cpp: In function 'void att(int)':
elephants.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int j = 0, k = 0; j < ord.size(); j++) {
| ~~^~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:82:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int j = 0, k = 0; j < ord.size(); j++) {
| ~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
21080 KB |
Output is correct |
2 |
Correct |
3 ms |
21080 KB |
Output is correct |
3 |
Correct |
4 ms |
21084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
21080 KB |
Output is correct |
2 |
Correct |
3 ms |
21080 KB |
Output is correct |
3 |
Correct |
4 ms |
21084 KB |
Output is correct |
4 |
Correct |
4 ms |
21084 KB |
Output is correct |
5 |
Correct |
4 ms |
21144 KB |
Output is correct |
6 |
Correct |
3 ms |
21084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
21080 KB |
Output is correct |
2 |
Correct |
3 ms |
21080 KB |
Output is correct |
3 |
Correct |
4 ms |
21084 KB |
Output is correct |
4 |
Correct |
4 ms |
21084 KB |
Output is correct |
5 |
Correct |
4 ms |
21144 KB |
Output is correct |
6 |
Correct |
3 ms |
21084 KB |
Output is correct |
7 |
Correct |
375 ms |
22372 KB |
Output is correct |
8 |
Correct |
472 ms |
22796 KB |
Output is correct |
9 |
Correct |
1255 ms |
26312 KB |
Output is correct |
10 |
Correct |
1113 ms |
26252 KB |
Output is correct |
11 |
Correct |
1089 ms |
26504 KB |
Output is correct |
12 |
Correct |
1983 ms |
26460 KB |
Output is correct |
13 |
Correct |
1624 ms |
26248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
21080 KB |
Output is correct |
2 |
Correct |
3 ms |
21080 KB |
Output is correct |
3 |
Correct |
4 ms |
21084 KB |
Output is correct |
4 |
Correct |
4 ms |
21084 KB |
Output is correct |
5 |
Correct |
4 ms |
21144 KB |
Output is correct |
6 |
Correct |
3 ms |
21084 KB |
Output is correct |
7 |
Correct |
375 ms |
22372 KB |
Output is correct |
8 |
Correct |
472 ms |
22796 KB |
Output is correct |
9 |
Correct |
1255 ms |
26312 KB |
Output is correct |
10 |
Correct |
1113 ms |
26252 KB |
Output is correct |
11 |
Correct |
1089 ms |
26504 KB |
Output is correct |
12 |
Correct |
1983 ms |
26460 KB |
Output is correct |
13 |
Correct |
1624 ms |
26248 KB |
Output is correct |
14 |
Correct |
892 ms |
23056 KB |
Output is correct |
15 |
Correct |
788 ms |
23428 KB |
Output is correct |
16 |
Correct |
3026 ms |
26412 KB |
Output is correct |
17 |
Correct |
4159 ms |
28864 KB |
Output is correct |
18 |
Correct |
4637 ms |
28732 KB |
Output is correct |
19 |
Correct |
3575 ms |
28492 KB |
Output is correct |
20 |
Correct |
3866 ms |
28776 KB |
Output is correct |
21 |
Correct |
3913 ms |
28716 KB |
Output is correct |
22 |
Correct |
3289 ms |
28448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
21080 KB |
Output is correct |
2 |
Correct |
3 ms |
21080 KB |
Output is correct |
3 |
Correct |
4 ms |
21084 KB |
Output is correct |
4 |
Correct |
4 ms |
21084 KB |
Output is correct |
5 |
Correct |
4 ms |
21144 KB |
Output is correct |
6 |
Correct |
3 ms |
21084 KB |
Output is correct |
7 |
Correct |
375 ms |
22372 KB |
Output is correct |
8 |
Correct |
472 ms |
22796 KB |
Output is correct |
9 |
Correct |
1255 ms |
26312 KB |
Output is correct |
10 |
Correct |
1113 ms |
26252 KB |
Output is correct |
11 |
Correct |
1089 ms |
26504 KB |
Output is correct |
12 |
Correct |
1983 ms |
26460 KB |
Output is correct |
13 |
Correct |
1624 ms |
26248 KB |
Output is correct |
14 |
Correct |
892 ms |
23056 KB |
Output is correct |
15 |
Correct |
788 ms |
23428 KB |
Output is correct |
16 |
Correct |
3026 ms |
26412 KB |
Output is correct |
17 |
Correct |
4159 ms |
28864 KB |
Output is correct |
18 |
Correct |
4637 ms |
28732 KB |
Output is correct |
19 |
Correct |
3575 ms |
28492 KB |
Output is correct |
20 |
Correct |
3866 ms |
28776 KB |
Output is correct |
21 |
Correct |
3913 ms |
28716 KB |
Output is correct |
22 |
Correct |
3289 ms |
28448 KB |
Output is correct |
23 |
Execution timed out |
9100 ms |
39316 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |