| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 251012 |
2020-07-19T23:09:58 Z |
Amine |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
25052 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){
pos.erase(a[l]);
a[l] = val;
pos[a[l]] = l;
st[idx] = {a[l],a[l]};
return;
}
if (l > p || r < p)
return;
int mid = (l + r) / 2;
update(idx << 1, l, mid, p, val);
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--;
set<int> s;
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 ;
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:98: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:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
~~~~~^~~~~~~~~~~~
cake.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
cake.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&c);
~~~~~^~~~~~~~~~
cake.cpp:114:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&b);
~~~~~^~~~~~~~~
cake.cpp:131:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&i,&e);
~~~~~^~~~~~~~~~~~~~~
cake.cpp:138:19: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
update(1, 0, n - 1, i, v);
~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1073 ms |
5636 KB |
Output isn't correct |
| 2 |
Incorrect |
728 ms |
5752 KB |
Output isn't correct |
| 3 |
Incorrect |
748 ms |
5656 KB |
Output isn't correct |
| 4 |
Incorrect |
654 ms |
5640 KB |
Output isn't correct |
| 5 |
Incorrect |
1153 ms |
6908 KB |
Output isn't correct |
| 6 |
Incorrect |
1064 ms |
7276 KB |
Output isn't correct |
| 7 |
Incorrect |
792 ms |
7032 KB |
Output isn't correct |
| 8 |
Incorrect |
673 ms |
7160 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
456 ms |
9464 KB |
Output isn't correct |
| 2 |
Incorrect |
340 ms |
9336 KB |
Output isn't correct |
| 3 |
Incorrect |
343 ms |
9336 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 5 |
Incorrect |
584 ms |
20216 KB |
Output isn't correct |
| 6 |
Incorrect |
669 ms |
20244 KB |
Output isn't correct |
| 7 |
Incorrect |
488 ms |
19960 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
126 ms |
1016 KB |
Output isn't correct |
| 2 |
Incorrect |
100 ms |
1272 KB |
Output isn't correct |
| 3 |
Incorrect |
254 ms |
5112 KB |
Output isn't correct |
| 4 |
Incorrect |
286 ms |
5008 KB |
Output isn't correct |
| 5 |
Incorrect |
318 ms |
1960 KB |
Output isn't correct |
| 6 |
Incorrect |
463 ms |
6776 KB |
Output isn't correct |
| 7 |
Incorrect |
372 ms |
3192 KB |
Output isn't correct |
| 8 |
Incorrect |
493 ms |
10104 KB |
Output isn't correct |
| 9 |
Execution timed out |
2067 ms |
24776 KB |
Time limit exceeded |
| 10 |
Incorrect |
1032 ms |
5112 KB |
Output isn't correct |
| 11 |
Incorrect |
1467 ms |
7368 KB |
Output isn't correct |
| 12 |
Execution timed out |
2072 ms |
22040 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2085 ms |
25052 KB |
Time limit exceeded |
