| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 251017 |
2020-07-20T00:03:41 Z |
Amine |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
30712 KB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define f first
#define s second
typedef long long ll;
typedef unsigned long long ull;
void IO(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("test.txt","r",stdin);
#endif
}
const int N=2e6+3,M=5e3+5,mod=1e9+7,dx[]={1,-1,0,0},
dy[]={0,0,1,-1};
const double eps=1e-9;
int n,m,k,tc,a[N],A,q;
char c;
map<int,int> pos;
set<int> s;
pair<int,int> st[N];
void build(int idx = 1, int l = 0, int r = n - 1){
if (l == r){
st[idx] = {a[l],a[l]};
return;
}
int mid = (l + r) >> 1;
build(idx << 1, l, mid);
build((idx << 1) + 1,mid + 1, r);
st[idx] = {min(st[idx << 1].f,st[(idx << 1) + 1].f),
max(st[idx << 1].s,st[(idx << 1) + 1].s)};
}
void update(int idx, int l, int r, int p, int val){
if (l == r){
s.erase(a[l]);
s.insert(val);
a[l] = val;
pos.erase(val);
pos[a[l]] = l;
st[idx] = {a[l],a[l]};
return;
}
int mid = (l + r) / 2;
if (l <= p && p <= mid)
update(idx << 1, l, mid, p, val);
else
update((idx << 1) + 1, mid + 1, r, p, val);
st[idx] = {min(st[idx << 1].f,st[(idx << 1) + 1].f),
max(st[idx << 1].s,st[(idx << 1) + 1].s)};
}
int query(int idx, int l, int r, int ql, int qr){
if (l >= ql && r <= qr)
return st[idx].s;
if (r < ql || l > qr)
return 0;
int mid = (l + r) / 2;
int ret = query(idx << 1, l, mid, ql, qr);
ret = max(ret, query((idx << 1) + 1, mid + 1, r, ql, qr));
return ret;
}
int bs(int l, int r, int x, bool rSide){
int ret = rSide ? n - 1 : 0;
while(l <= r){
int mid = (l + r) >> 1;
if (rSide){
int mx = query(1, 0, n - 1, l, mid);
if (mx >= x)
r = mid - 1, ret = mid - 1;
else
l = mid + 1;
}
else{
int mx = query(1, 0, n - 1, mid, r);
if (mx >= x)
l = mid + 1, ret = mid + 1;
else
r = mid - 1;
}
}
return ret;
}
int main(){
scanf("%d%d",&n,&A);
A--;
for(int i = 0 ; i < n ; i++){
scanf("%d",&a[i]);
s.insert(a[i]);
pos[a[i]] = i;
if (sz(s) > 10)
s.erase(s.begin());
}
build();
scanf("%d",&q);
while(q--){
scanf(" %c",&c);
int b,i,e;
if (c == 'F'){
scanf("%d",&b);
b--;
if (A == b)
printf("0");
else if (b < A){
int x = query(1, 0, n - 1, b, A - 1);
int y = bs(A + 1, n - 1, x, true);
printf("%d", abs(A - y) + abs(A - b));
}
else{
int x = query(1, 0, n - 1, A + 1, b);
int y = bs(0, A - 1, x, false);
printf("%d", abs(A - y) + abs(A - b));
}
printf("\n");
}
else{
scanf("%d %d",&i,&e);
int v = *s.rbegin() + 1;
e--;
i--;
for(auto it = s.rbegin() ; e ; it++,e--){
v = *it;
update(1, 0, n - 1, pos[*it], (*it)+1);
}
update(1, 0, n - 1, i, v);
if (sz(s) > 10)
s.erase(s.begin());
}
}
}
Compilation message
cake.cpp: In function 'void IO()':
cake.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("test.txt","r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cake.cpp: In function 'int main()':
cake.cpp:100: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:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
~~~~~^~~~~~~~~~~~
cake.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
cake.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&c);
~~~~~^~~~~~~~~~
cake.cpp:115:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&b);
~~~~~^~~~~~~~~
cake.cpp:132:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&i,&e);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
11 ms |
512 KB |
Output is correct |
| 5 |
Correct |
32 ms |
1528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1109 ms |
24464 KB |
Output is correct |
| 2 |
Correct |
610 ms |
24568 KB |
Output is correct |
| 3 |
Correct |
730 ms |
24568 KB |
Output is correct |
| 4 |
Correct |
427 ms |
24568 KB |
Output is correct |
| 5 |
Correct |
1142 ms |
25596 KB |
Output is correct |
| 6 |
Correct |
965 ms |
25848 KB |
Output is correct |
| 7 |
Correct |
758 ms |
25656 KB |
Output is correct |
| 8 |
Correct |
438 ms |
25760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
475 ms |
8056 KB |
Output is correct |
| 2 |
Correct |
330 ms |
8056 KB |
Output is correct |
| 3 |
Correct |
309 ms |
7928 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
573 ms |
17912 KB |
Output is correct |
| 6 |
Correct |
618 ms |
17844 KB |
Output is correct |
| 7 |
Correct |
472 ms |
17656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
1784 KB |
Output is correct |
| 2 |
Correct |
96 ms |
1976 KB |
Output is correct |
| 3 |
Correct |
228 ms |
5920 KB |
Output is correct |
| 4 |
Correct |
271 ms |
5968 KB |
Output is correct |
| 5 |
Correct |
358 ms |
4472 KB |
Output is correct |
| 6 |
Correct |
455 ms |
8792 KB |
Output is correct |
| 7 |
Correct |
372 ms |
6228 KB |
Output is correct |
| 8 |
Correct |
377 ms |
16736 KB |
Output is correct |
| 9 |
Execution timed out |
2068 ms |
30188 KB |
Time limit exceeded |
| 10 |
Correct |
1230 ms |
13480 KB |
Output is correct |
| 11 |
Correct |
1503 ms |
15096 KB |
Output is correct |
| 12 |
Execution timed out |
2090 ms |
28024 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2080 ms |
30712 KB |
Time limit exceeded |
