| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 363423 |
2021-02-05T21:49:25 Z |
nickmet2004 |
Cake (CEOI14_cake) |
C++11 |
|
0 ms |
0 KB |
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 200;
int n , s , q , a[N] ,p;
int T[1<<20]
vector<int> top10;
void upd(int d , int id , int l = 1 , int r = n, int pos = 1){
if(id > r || id < l) return;
if(l == r){
T[pos] = d; return;
}
int mid = (l + r) >> 1;
upd(d , id, l , mid , pos * 2); upd(d , id , mid + 1 , r , pos * 2 + 1);
T[pos] = max(T[pos * 2 ] , T[pos * 2 + 1]);
}
int get(int L , int R , int l = 1, int r= n , int pos = 1){
if(r < L || R < l) return -1;
if(L <= l && r <= R)return T[pos];
int mid = (l + r)>>1;
return max(get(L ,R , l , mid , pos * 2) , get(L , R , mid + 1, r , pos * 2 +1));
}
int go1(int L , int R , int x , int l = 1, int r = n , int pos = 1){
if(R < l || r < L) return -1;
if(L <= l && r <= R){
if(T[pos] <= x) return -1;
while(l != r){
int mid = (l + r) >> 1;
if(T[pos * 2] > x) pos = pos * 2 , r = mid;
else pos = pos * 2 + 1 , l = mid + 1;
}
return l;
}
int mid = (l + r) >> 1;
int Left = go1(L , R , x , l , mid , pos * 2);
if(Left != -1) return Left;
return go1(L , R , x , mid + 1 , r ,pos * 2 + 1);
}
int go2(int L , int R , int x, int l = 1 , int r =n , int pos = 1){
if(R < l || r < L) return -1;
if(L <= l && r <= R){
if(T[pos] <= x) return -1;
while(l != r){
int mid = (l + r) >> 1;
if(T[pos * 2 + 1] > x) pos = pos * 2 + 1 , l = mid + 1;
else pos = pos * 2 , r = mid;
}
return l;
}
int mid = (l + r) >> 1;
int Right = go2(L , R , x , mid + 1 , r , pos * 2 + 1);
if(Right != -1) return Right;
return go2(L , R , x , l , mid , pos * 2);
}
int main (){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> s;
for(int i = 1; i <= n; ++i) cin >> a[i] , top10.emplace_back(i);
for(int i = 1; i <= n; ++i) upd(a[i] , i);
sort(top10.begin() , top10.end(), [&](int i , int j){
return a[i] > a[j];
});
while(top10.size() > 10) top10.pop_back();
//for(int x : top10) cout << x << " ";
cin >> q;
p = n;
while(q--){
char c;
cin >> c;
if(c == 'E'){
int id, rnk;
cin >> id >> rnk;
for(int j =0; j < top10.size(); ++j){
if(top10[j] == id) {top10.erase(top10.begin() + j); break;}
}
rnk--;
top10.insert(top10.begin() + rnk, id);
while(top10.size() > 10) top10.pop_back();
for(int j = rnk; ~j; --j) upd(++p , top10[j]);
//for(int j = 0; j < top10.size(); ++j) cout << top10[j] << " ";cout <<endl;
} else {
int F;
cin >> F;
if(F ==s){cout << 0 << endl; continue;}
if(F < s){
int mx = get(F , s - 1);
//cout << "hii" << endl;
int y = go1(s + 1 , n , mx);
if(y == -1) cout << n - F << endl;
else cout << y - F - 1<< endl;
} else {
int mx = get(s + 1 , F);
int y = go2(1 , s-1, mx);
if(y == -1) cout << F-1 << endl;
else cout << F - y - 1 << endl;
//cout << F << " F " << y << " y " << endl;
}
}
}
return 0;
}
Compilation message
cake.cpp:7:1: error: expected initializer before 'vector'
7 | vector<int> top10;
| ^~~~~~
cake.cpp: In function 'void upd(int, int, int, int, int)':
cake.cpp:11:9: error: 'T' was not declared in this scope
11 | T[pos] = d; return;
| ^
cake.cpp:15:5: error: 'T' was not declared in this scope
15 | T[pos] = max(T[pos * 2 ] , T[pos * 2 + 1]);
| ^
cake.cpp: In function 'int get(int, int, int, int, int)':
cake.cpp:19:32: error: 'T' was not declared in this scope
19 | if(L <= l && r <= R)return T[pos];
| ^
cake.cpp: In function 'int go1(int, int, int, int, int, int)':
cake.cpp:26:12: error: 'T' was not declared in this scope
26 | if(T[pos] <= x) return -1;
| ^
cake.cpp:29:16: error: 'T' was not declared in this scope
29 | if(T[pos * 2] > x) pos = pos * 2 , r = mid;
| ^
cake.cpp: In function 'int go2(int, int, int, int, int, int)':
cake.cpp:42:12: error: 'T' was not declared in this scope
42 | if(T[pos] <= x) return -1;
| ^
cake.cpp:45:16: error: 'T' was not declared in this scope
45 | if(T[pos * 2 + 1] > x) pos = pos * 2 + 1 , l = mid + 1;
| ^
cake.cpp: In function 'int main()':
cake.cpp:58:47: error: 'top10' was not declared in this scope
58 | for(int i = 1; i <= n; ++i) cin >> a[i] , top10.emplace_back(i);
| ^~~~~
cake.cpp:60:10: error: 'top10' was not declared in this scope
60 | sort(top10.begin() , top10.end(), [&](int i , int j){
| ^~~~~
