| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 105062 |
2019-04-10T11:54:47 Z |
groeneprof |
Cake (CEOI14_cake) |
C++14 |
|
1073 ms |
21692 KB |
#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
#define st ts[tree]
using namespace std;
const bool debug = 0;
vector<int> ts[2];
int N, A, Q;
vector<int> d;
int update(int i, int val, int u = 0, int L = 0, int R = N, int tree = -1){
if(tree == -1) tree = (i>=A)?1:0;
//cout<<"u "<<i<<" "<<val<<" "<<u<<" "<<L<<" "<<R<<" "<<tree<<endl;
if(i<L||i>R){
return st[u];
}
if(L==R){
return st[u] = val;
}
st[u] = max(update(i, val, u*2+1, L, (L+R)/2, tree), update(i, val, u*2+2, (L+R)/2+1, R, tree));
//cout<<"u "<<i<<" "<<val<<" "<<u<<" "<<L<<" "<<R<<" "<<tree<<"updates to "<<st[u]<<endl;
return st[u];
}
int query(int i, int j, int u = 0, int L = 0, int R = N, int tree = -1){
if(tree == -1) tree = (i>=A)?1:0;
//cout<<"q "<<i<<" "<<j<<" "<<u<<" "<<L<<" "<<R<<" "<<tree<<" "<<st[u]<<endl;
if(j<L||i>R){
return 0;
}
if(L>=i&&R<=j){
return st[u];
}
return max(query(i, j, u*2+1, L, (L+R)/2, tree), query(i, j, u*2+2, (L+R)/2+1, R, tree));
}
int binsearch1(int val, int u = 0, int L = 0, int R = N, int tree = 1){ //search to the right of a
if(L == R) {
return L;
}
if(st[u*2+1] > val){ //the element we are looking for is in the first subtree
return binsearch1(val, u*2+1, L, (L+R)/2, tree);
}
else{ //not
return binsearch1(val, u*2+2, (L+R)/2+1, R, tree);
}
}
int binsearch0(int val, int u = 0, int L = 0, int R = N, int tree = 0){
//cout<<"bs "<<val<<" "<<u<<" "<<L<<" "<<R<<" "<<tree<<endl;
if(L==R){
return L;
}
if(st[u*2+2] > val){ //it's in the right subtree
return binsearch0(val, u*2+2, (L+R)/2+1, R, tree);
}
else{
return binsearch0(val, u*2+1, L, (L+R)/2, tree);
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>N>>A;
A--;
d.resize(N);
ts[0].resize(4*N, 0);
ts[1].resize(4*N, 0);
vector<int> top;
F(i, N){
int a;
cin>>a;
d[i]=a;
update(i,a);
}
H((int)(1e18));
update(N, 1e18);
cin>>Q;
auto copy = d;
sort(copy.begin(), copy.end());
//cout<<"aaaaaaaa"<<endl;
FR(i, N-10, N){
top.push_back(copy[i]);
}
//cout<<"bbbbbbbbbb"<<endl;
F(i, Q){
char c;
cin>>c;
if(c=='E'){
int j, e;
cin>>j>>e;
j--;
e--;
vector<int>::iterator it = find(top.begin(), top.end(), j);
//cout<<"aaaa"<<endl;
if(it!=top.end()){
//cout<<"bbbb"<<endl;
if(e==0){
//cout<<"cccc"<<endl;
d[j] = d[top[0]]+(int)(1<<15);
if(j!=A) update(j, d[j]);
top.insert(top.begin()+e, j);
//cout<<"cccc"<<endl;
}
else{
top.insert(top.begin()+e, j);
if(d[top[e-1]]-d[top[e+1]]==1){
int start = d[0]+(int)(20*(1<<15));
for(int k = 0; k<11; k++){
d[top[k]] = start-k*(int)(1<<15);
if(top[k]!=A)update(top[k], d[top[k]]);
}
}
else{
d[j] = (d[top[e-1]]+d[top[e+1]])/2;
if(j!=A) update(j, d[j]);
}
}
top.erase(it+1);
}
else{
P("eeee");
if(e==0){
P("ffff");
d[j] = d[top[0]]+(int)(1<<15);
if(j!=A) update(j, d[j]);
top.insert(top.begin()+e, j);
}
else{
P("ggGG");
top.insert(top.begin()+e, j);
if(d[top[e-1]]-d[top[e+1]]==1){
int start = d[0]+(int)(20*(1<<15));
//cout<<"nice"<<endl;
for(int k = 0; k<11 && k<(int)(top.size()); k++){
d[top[k]] = start-k*(int)(1ll<<15ll);
if(top[k]!=A) update(top[k], d[top[k]]);
}
}
else{
d[j] = (d[top[e-1]]+d[top[e+1]])/2ll;
if(j!=A) update(j, d[j]);
}
}
top.erase(top.end()-1);
}
}
else if(c == 'F'){
int b;
cin>>b;
b--;
if(b == A){
cout<<0<<endl;
continue;
}
else if(b<A){
P(1);
int M = query(b, A);
H(M);
int C = binsearch1(M);
H(C << "-" << b);
cout<<min(N-1,C-1)-b<<endl;
}
else{
P(0);
int M = query(A, b);
H(M);
int C = binsearch0(M);
H(C);
if(d[C]>M) C++;
cout<<b-C<<endl;
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
225 ms |
1144 KB |
Output isn't correct |
| 2 |
Incorrect |
222 ms |
1184 KB |
Output isn't correct |
| 3 |
Incorrect |
193 ms |
1272 KB |
Output isn't correct |
| 4 |
Correct |
208 ms |
1204 KB |
Output is correct |
| 5 |
Incorrect |
239 ms |
2336 KB |
Output isn't correct |
| 6 |
Incorrect |
249 ms |
2360 KB |
Output isn't correct |
| 7 |
Incorrect |
287 ms |
2552 KB |
Output isn't correct |
| 8 |
Correct |
197 ms |
2432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
259 ms |
8808 KB |
Output isn't correct |
| 2 |
Incorrect |
309 ms |
8708 KB |
Output isn't correct |
| 3 |
Incorrect |
235 ms |
8824 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
366 ms |
20728 KB |
Output isn't correct |
| 6 |
Incorrect |
337 ms |
20664 KB |
Output isn't correct |
| 7 |
Incorrect |
313 ms |
20344 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
640 KB |
Output isn't correct |
| 2 |
Incorrect |
69 ms |
896 KB |
Output isn't correct |
| 3 |
Incorrect |
156 ms |
4604 KB |
Output isn't correct |
| 4 |
Incorrect |
154 ms |
4468 KB |
Output isn't correct |
| 5 |
Incorrect |
176 ms |
888 KB |
Output isn't correct |
| 6 |
Incorrect |
247 ms |
6136 KB |
Output isn't correct |
| 7 |
Incorrect |
251 ms |
1784 KB |
Output isn't correct |
| 8 |
Incorrect |
171 ms |
8284 KB |
Output isn't correct |
| 9 |
Incorrect |
1073 ms |
21680 KB |
Output isn't correct |
| 10 |
Incorrect |
555 ms |
1656 KB |
Output isn't correct |
| 11 |
Incorrect |
741 ms |
3344 KB |
Output isn't correct |
| 12 |
Incorrect |
1073 ms |
17728 KB |
Output isn't correct |
| 13 |
Incorrect |
881 ms |
21692 KB |
Output isn't correct |
