| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 164656 |
2019-11-22T11:15:57 Z |
arnold518 |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
23416 KB |
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 250000;
const int MAXQ = 500000;
int N, Q, A, D[MAXN+10];
set<pii, greater<pii>> S;
int tree[4*MAXN+10];
void init(int node, int tl, int tr)
{
if(tl==tr)
{
tree[node]=D[tl];
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
tree[node]=max(tree[node*2], tree[node*2+1]);
}
void update(int node, int tl, int tr, int pos, int val)
{
if(tl==tr)
{
tree[node]=val;
return;
}
int mid=tl+tr>>1;
if(pos<=mid) update(node*2, tl, mid, pos, val);
else update(node*2+1, mid+1, tr, pos, val);
tree[node]=max(tree[node*2], tree[node*2+1]);
}
int query(int node, int tl, int tr, int l, int r)
{
if(l<=tl && tr<=r) return tree[node];
if(r<tl || tr<l) return 0;
int mid=tl+tr>>1;
return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
}
int main()
{
int i, j;
scanf("%d%d", &N, &A);
for(i=1; i<=N; i++) scanf("%d", &D[i]), S.insert({D[i], i});
D[0]=D[N+1]=987654321;
init(1, 0, N+1);
scanf("%d", &Q);
while(Q--)
{
char t;
scanf(" %c", &t);
if(t=='F')
{
int x;
scanf("%d", &x);
if(x==A) printf("0\n");
else if(x<A)
{
int lo=A, hi=N+1;
int val=query(1, 0, N+1, x, A-1);
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(query(1, 0, N+1, A+1, mid)>val) hi=mid;
else lo=mid;
}
printf("%d\n", hi-x-1);
}
else
{
int lo=0, hi=A;
int val=query(1, 0, N+1, A+1, x);
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(query(1, 0, N+1, mid, A-1)>val) lo=mid;
else hi=mid;
}
printf("%d\n", x-lo-1);
}
}
else
{
int a, b;
scanf("%d%d", &a, &b); b--;
S.erase({D[a], a});
vector<pii> T;
auto it=S.begin();
for(i=0; i<b; i++, it++) T.push_back(*it);
int val=S.begin()->first+2;
for(auto it : T)
{
S.erase(it);
D[it.second]++;
S.insert({D[it.second], it.second});
update(1, 0, N+1, it.second, D[it.second]);
val=min(val, D[it.second]);
}
val--;
D[a]=val;
S.insert({D[a], a});
update(1, 0, N+1, a, D[a]);
}
}
}
Compilation message
cake.cpp: In function 'void init(int, int, int)':
cake.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
cake.cpp: In function 'void update(int, int, int, int, int)':
cake.cpp:39:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
cake.cpp: In function 'int query(int, int, int, int, int)':
cake.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
cake.cpp: In function 'int main()':
cake.cpp:79:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=lo+hi>>1;
~~^~~
cake.cpp:91:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=lo+hi>>1;
~~^~~
cake.cpp:55:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
cake.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &A);
~~~~~^~~~~~~~~~~~~~~~
cake.cpp:58:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=N; i++) scanf("%d", &D[i]), S.insert({D[i], i});
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
cake.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
cake.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &t);
~~~~~^~~~~~~~~~~
cake.cpp:71:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
cake.cpp:101:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b); b--;
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
11 ms |
504 KB |
Output is correct |
| 5 |
Correct |
30 ms |
1144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
765 ms |
5372 KB |
Output is correct |
| 2 |
Correct |
380 ms |
5496 KB |
Output is correct |
| 3 |
Correct |
468 ms |
5368 KB |
Output is correct |
| 4 |
Correct |
312 ms |
5384 KB |
Output is correct |
| 5 |
Correct |
832 ms |
6520 KB |
Output is correct |
| 6 |
Correct |
677 ms |
7004 KB |
Output is correct |
| 7 |
Correct |
548 ms |
6776 KB |
Output is correct |
| 8 |
Correct |
313 ms |
7160 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
479 ms |
8364 KB |
Output is correct |
| 2 |
Correct |
302 ms |
8356 KB |
Output is correct |
| 3 |
Correct |
315 ms |
8312 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
591 ms |
18400 KB |
Output is correct |
| 6 |
Correct |
715 ms |
18296 KB |
Output is correct |
| 7 |
Correct |
503 ms |
18088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
95 ms |
1364 KB |
Output is correct |
| 3 |
Correct |
256 ms |
4724 KB |
Output is correct |
| 4 |
Correct |
265 ms |
4572 KB |
Output is correct |
| 5 |
Correct |
275 ms |
1960 KB |
Output is correct |
| 6 |
Correct |
499 ms |
6400 KB |
Output is correct |
| 7 |
Correct |
357 ms |
3152 KB |
Output is correct |
| 8 |
Correct |
353 ms |
9080 KB |
Output is correct |
| 9 |
Execution timed out |
2047 ms |
22556 KB |
Time limit exceeded |
| 10 |
Correct |
908 ms |
5320 KB |
Output is correct |
| 11 |
Correct |
1345 ms |
7328 KB |
Output is correct |
| 12 |
Execution timed out |
2064 ms |
19876 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2065 ms |
23416 KB |
Time limit exceeded |
