//#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN = 15e4+1, sqr = 500;
int n, pos[MAXN], cnt = 0, seg[MAXN], l, last = 0;
vector <pair<int,int>> dp[sqr], pts;
vector <int> all[sqr], tmp;
//multiset <pair<int,int>> el;
void init(int N, int L, int X[]){
n = N; l = L;
for(int i = 0; i < n; i++){
pos[i] = X[i];
}
}
void caldp(int ind){
for(int i = 0; i < (int)all[ind].size(); i++) dp[ind].push_back({0,0});
int id = (int)all[ind].size();
for(int i = (int)all[ind].size()-1; i>=0; i--){
//int id = upper_bound(all[ind].begin(), all[ind].end(), all[ind][i]+l) - all[ind].begin();
while(id > 0 && all[ind][id-1] > all[ind][i]+l) id--;
if(id >= (int)all[ind].size()){
dp[ind][i].first = 1; dp[ind][i].second = all[ind][i]+l+1;
continue;
}
dp[ind][i].first = dp[ind][id].first+1; dp[ind][i].second = dp[ind][id].second;
}
return;
}
void build(){
// cout << "build!!" << endl;
// el.clear();
pts.clear();
for(int i = 0; i < n; i++) pts.push_back({pos[i], i});
for(int i = 0; i < last; i++) all[i].clear(), dp[i].clear();
sort(pts.begin(), pts.end());
int pt = 0, c = 0;
while(pt < n){
while(pt < n && (int)all[c].size() < sqr){
all[c].push_back(pts[pt].first);
seg[pts[pt].second] = c; pt++;
}
caldp(c);
c++;
}
last = c;
// for(int i = 0; i < n; i++) el.insert({pos[i], seg[i]});
return;
}
void del(int ind, int val){
while(all[ind].back() != val){
tmp.push_back(all[ind].back());
all[ind].pop_back();
}
all[ind].pop_back();
while(!tmp.empty()){
all[ind].push_back(tmp.back());
tmp.pop_back();
}
dp[ind].clear(); caldp(ind);
return;
}
void add(int ind, int val){
while(!all[ind].empty() && all[ind].back() > val){
tmp.push_back(all[ind].back());
all[ind].pop_back();
}
all[ind].push_back(val);
while(!tmp.empty()){
all[ind].push_back(tmp.back());
tmp.pop_back();
}
dp[ind].clear(); caldp(ind);
return;
}
int get(){
int cur = all[0][0], res = 0, pt = 0;
while(pt < last){
while(pt < last && cur > all[pt].back()) pt++;
if(pt >= last) break;
int ind = pt;
int id = lower_bound(all[ind].begin(), all[ind].end(), cur) - all[ind].begin();
res += dp[ind][id].first; cur = dp[ind][id].second;
}
return res;
}
int update(int i, int y){
if(cnt % (sqr-3) == 0) build();
del(seg[i],pos[i]);
int pt = 0;
while(pt+1 < last && y > all[pt+1][0]) pt++;
add(pt, y);
seg[i] = pt; pos[i] = y;
int ans = get(); cnt++;
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// init(NN, L1, tof);
cin >> n >> l;
for(int i = 0; i < n; i++) cin >> pos[i];
cout << update(2,16) << endl;
cout << update(1,25) << endl;
cout << update(3,35) << endl;
cout << update(0,38) << endl;
cout << update(2,0) << endl;
return 0;
}*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
859 ms |
1428 KB |
Output is correct |
| 8 |
Correct |
889 ms |
1640 KB |
Output is correct |
| 9 |
Correct |
891 ms |
2696 KB |
Output is correct |
| 10 |
Correct |
889 ms |
2532 KB |
Output is correct |
| 11 |
Correct |
856 ms |
2660 KB |
Output is correct |
| 12 |
Correct |
1387 ms |
2796 KB |
Output is correct |
| 13 |
Correct |
903 ms |
2660 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
859 ms |
1428 KB |
Output is correct |
| 8 |
Correct |
889 ms |
1640 KB |
Output is correct |
| 9 |
Correct |
891 ms |
2696 KB |
Output is correct |
| 10 |
Correct |
889 ms |
2532 KB |
Output is correct |
| 11 |
Correct |
856 ms |
2660 KB |
Output is correct |
| 12 |
Correct |
1387 ms |
2796 KB |
Output is correct |
| 13 |
Correct |
903 ms |
2660 KB |
Output is correct |
| 14 |
Correct |
913 ms |
2024 KB |
Output is correct |
| 15 |
Correct |
1325 ms |
2280 KB |
Output is correct |
| 16 |
Correct |
2131 ms |
2868 KB |
Output is correct |
| 17 |
Correct |
2324 ms |
3800 KB |
Output is correct |
| 18 |
Correct |
2480 ms |
3680 KB |
Output is correct |
| 19 |
Correct |
1705 ms |
3552 KB |
Output is correct |
| 20 |
Correct |
2328 ms |
3680 KB |
Output is correct |
| 21 |
Correct |
2316 ms |
4064 KB |
Output is correct |
| 22 |
Correct |
1495 ms |
3552 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
859 ms |
1428 KB |
Output is correct |
| 8 |
Correct |
889 ms |
1640 KB |
Output is correct |
| 9 |
Correct |
891 ms |
2696 KB |
Output is correct |
| 10 |
Correct |
889 ms |
2532 KB |
Output is correct |
| 11 |
Correct |
856 ms |
2660 KB |
Output is correct |
| 12 |
Correct |
1387 ms |
2796 KB |
Output is correct |
| 13 |
Correct |
903 ms |
2660 KB |
Output is correct |
| 14 |
Correct |
913 ms |
2024 KB |
Output is correct |
| 15 |
Correct |
1325 ms |
2280 KB |
Output is correct |
| 16 |
Correct |
2131 ms |
2868 KB |
Output is correct |
| 17 |
Correct |
2324 ms |
3800 KB |
Output is correct |
| 18 |
Correct |
2480 ms |
3680 KB |
Output is correct |
| 19 |
Correct |
1705 ms |
3552 KB |
Output is correct |
| 20 |
Correct |
2328 ms |
3680 KB |
Output is correct |
| 21 |
Correct |
2316 ms |
4064 KB |
Output is correct |
| 22 |
Correct |
1495 ms |
3552 KB |
Output is correct |
| 23 |
Correct |
5186 ms |
6940 KB |
Output is correct |
| 24 |
Correct |
5614 ms |
11960 KB |
Output is correct |
| 25 |
Correct |
4694 ms |
12144 KB |
Output is correct |
| 26 |
Correct |
6057 ms |
11868 KB |
Output is correct |
| 27 |
Correct |
6797 ms |
11824 KB |
Output is correct |
| 28 |
Correct |
2801 ms |
5356 KB |
Output is correct |
| 29 |
Correct |
2743 ms |
5356 KB |
Output is correct |
| 30 |
Correct |
2804 ms |
5356 KB |
Output is correct |
| 31 |
Correct |
2751 ms |
5312 KB |
Output is correct |
| 32 |
Correct |
4981 ms |
11356 KB |
Output is correct |
| 33 |
Correct |
4848 ms |
10716 KB |
Output is correct |
| 34 |
Correct |
5238 ms |
11484 KB |
Output is correct |
| 35 |
Correct |
5290 ms |
14480 KB |
Output is correct |
| 36 |
Correct |
3936 ms |
11356 KB |
Output is correct |
| 37 |
Correct |
7950 ms |
14300 KB |
Output is correct |
| 38 |
Correct |
5156 ms |
10588 KB |
Output is correct |
| 39 |
Correct |
5692 ms |
11612 KB |
Output is correct |
| 40 |
Correct |
5357 ms |
10588 KB |
Output is correct |
| 41 |
Correct |
8148 ms |
11612 KB |
Output is correct |
| 42 |
Correct |
8306 ms |
11996 KB |
Output is correct |
