| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 114114 |
2019-05-30T11:57:28 Z |
dndhk |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
15412 KB |
#include <bits/stdc++.h>
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 250000;
int N, C, Q;
int arr[MAX_N+1];
vector<int> v;
struct SEG{
SEG(int l, int r, int mx) : l(l), r(r), mx(mx) {}
int l, r;
int mx;
};
vector<SEG> seg;
void init(int idx, int s, int e){
if(s==e) return;
seg[idx].l = seg.size(); seg.pb({-1, -1, 0});
seg[idx].r = seg.size(); seg.pb({-1, -1, 0});
init(seg[idx].l, s, (s+e)/2);
init(seg[idx].r, (s+e)/2+1, e);
}
void update(int idx, int s, int e, int x, int y){
if(s==e){
seg[idx].mx = y;
return;
}
if(x<=(s+e)/2){
update(seg[idx].l, s, (s+e)/2, x, y);
}else{
update(seg[idx].r, (s+e)/2+1, e, x, y);
}
seg[idx].mx = max(seg[seg[idx].l].mx, seg[seg[idx].r].mx);
}
int max(int idx, int s, int e, int x, int y){
if(x<=s && e<=y) return seg[idx].mx;
if(x>e || s>y) return 0;
return max(max(seg[idx].l, s, (s+e)/2, x, y), max(seg[idx].r, (s+e)/2+1, e, x, y));
}
int ans(int x){
if(C==x) return 0;
if(x>C){
int t = max(0, 1, N, C+1, x);
int s = 1, e = C, m;
while(s<e){
m = (s+e)/2;
if(max(0, 1, N, m, C-1)>t){
s = m+1;
}else{
e = m;
}
}
return x - s;
}else{
int t = max(0, 1, N, x, C-1);
//cout<<t<<endl;
int s = C, e = N, m;
while(s<e){
m = (s+e)/2+1;
if(max(0, 1, N, C+1, m)>t){
e = m-1;
}else{
s = m;
}
}
return s - x;
}
}
int maxarr;
void change(int x, int y){
y--;
int idx = -1;
for(int i=0; i<v.size(); i++){
if(v[i]==x){
idx = i;
break;
}
}
if(idx==-1){
for(int i=v.size(); i>=y+1; i--){
v[i] = v[i-1];
}
v[y] = x;
}else{
for(int j=idx; j>=y+1; j--){
v[j] = v[j-1];
}
v[y] = x;
}
for(int i=0; i<v.size(); i++){
update(0, 1, N, v[i], maxarr+10-i);
}
maxarr += 10;
}
int main(){
seg.pb({-1, -1, 0});
scanf("%d%d", &N, &C);
init(0, 1, N);
maxarr = N;
for(int i=1; i<=N; i++){
scanf("%d", &arr[i]);
update(0, 1, N, i, arr[i]);
}
for(int i=N; i>=max(1, N-9); i--){
for(int j=1; j<=N; j++){
if(arr[j]==i){
v.pb(j);
break;
}
}
}
scanf("%d", &Q);
for(int i=0; i<Q; i++){
string str;
cin>>str;
if(str[0]=='F'){
int x;
scanf("%d", &x);
printf("%d\n", ans(x));
}else{
int x, y;
scanf("%d%d", &x, &y);
change(x, y);
}
}
return 0;
}
Compilation message
cake.cpp: In function 'void change(int, int)':
cake.cpp:100:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++){
~^~~~~~~~~
cake.cpp:117:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++){
~^~~~~~~~~
cake.cpp: In function 'int main()':
cake.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &C);
~~~~~^~~~~~~~~~~~~~~~
cake.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &arr[i]);
~~~~~^~~~~~~~~~~~~~~
cake.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
cake.cpp:147:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
cake.cpp:151:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
256 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
18 ms |
512 KB |
Output is correct |
| 5 |
Correct |
29 ms |
892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
569 ms |
5124 KB |
Output is correct |
| 2 |
Correct |
534 ms |
5276 KB |
Output is correct |
| 3 |
Correct |
555 ms |
5252 KB |
Output is correct |
| 4 |
Correct |
517 ms |
5268 KB |
Output is correct |
| 5 |
Correct |
656 ms |
5860 KB |
Output is correct |
| 6 |
Correct |
622 ms |
6368 KB |
Output is correct |
| 7 |
Correct |
640 ms |
6080 KB |
Output is correct |
| 8 |
Correct |
572 ms |
6268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
594 ms |
5272 KB |
Output is correct |
| 2 |
Correct |
469 ms |
5128 KB |
Output is correct |
| 3 |
Correct |
459 ms |
5104 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
653 ms |
10588 KB |
Output is correct |
| 6 |
Correct |
677 ms |
10428 KB |
Output is correct |
| 7 |
Correct |
597 ms |
10328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
988 KB |
Output is correct |
| 2 |
Correct |
132 ms |
1308 KB |
Output is correct |
| 3 |
Correct |
290 ms |
3100 KB |
Output is correct |
| 4 |
Correct |
243 ms |
3048 KB |
Output is correct |
| 5 |
Correct |
299 ms |
1912 KB |
Output is correct |
| 6 |
Correct |
562 ms |
4324 KB |
Output is correct |
| 7 |
Correct |
474 ms |
2804 KB |
Output is correct |
| 8 |
Correct |
330 ms |
5732 KB |
Output is correct |
| 9 |
Execution timed out |
2041 ms |
15180 KB |
Time limit exceeded |
| 10 |
Correct |
1014 ms |
5368 KB |
Output is correct |
| 11 |
Correct |
1340 ms |
6824 KB |
Output is correct |
| 12 |
Execution timed out |
2057 ms |
13500 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2063 ms |
15412 KB |
Time limit exceeded |
