# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
25979 |
2017-06-25T09:41:08 Z |
카제비(#1091) |
Cake (CEOI14_cake) |
C++14 |
|
1259 ms |
14948 KB |
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;
const int MAX_N = 3e5 + 100, MAX_Q = 5e5 + 100;
int N, X, Q, Nr[MAX_N];
vector<int> Ls, Rs;
set<pi> S;
void changeNr(int ix, int v) {
S.erase(pi(Nr[ix], ix));
vector<pi> Save;
for(int i=0; i+1<v; i++) {
auto it = S.end(); it--;
pi now = *it; now.one++;
Save.push_back(now);
Nr[now.two] = now.one;
S.erase(it);
}
auto it = S.end(); it--;
pi now = *it;
Nr[ix] = now.one + 1;
S.insert(pi(now.one+1, ix));
for(pi &e : Save) S.insert(e);
}
void setNr(int ix, int v) {
changeNr(ix, v);
// for(pi e : S) printf("[%d %d] ", e.one, e.two); puts("");
if(ix == X) return;
vector<int> temp;
if(ix < X) {
while(!Ls.empty() && Ls.back() <= ix) temp.push_back(Ls.back()), Ls.pop_back();
if(temp.empty() || temp.back() != ix) temp.push_back(ix);
for(int i=SZ(temp)-1; i>=0; i--)
if(Ls.empty() || Nr[Ls.back()] < Nr[temp[i]])
Ls.push_back(temp[i]);
} else {
while(!Rs.empty() && Rs.back() >= ix) temp.push_back(Rs.back()), Rs.pop_back();
if(temp.empty() || temp.back() != ix) temp.push_back(ix);
for(int i=SZ(temp)-1; i>=0; i--)
if(Rs.empty() || Nr[Rs.back()] < Nr[temp[i]])
Rs.push_back(temp[i]);
}
// printf("[Ls Rs]\n"); for(int l : Ls) printf("%d ", l); puts(""); for(int r : Rs) printf("%d ", r); puts("");
}
int getAns(int ix) {
if(ix == X) return 0;
int ans = abs(X - ix);
// printf("ix = %d\n", ix);
if(ix < X) {
int l = lower_bound(ALL(Ls), ix-1, [&](int a, int b) {
return a > b;
}) - Ls.begin() - 1;
int r = SZ(Rs);
for(int a=0, b=SZ(Rs)-1; a<=b; ) {
int m = (a+b) >> 1;
if(Nr[Rs[m]] > Nr[Ls[l]]) r = m, b = m-1; else a = m+1;
}
// printf("left [%d] | [%d]\n", l, r);
int rix = N+1;
if(r < SZ(Rs)) rix = Rs[r];
ans += abs(rix - X - 1);
} else {
int r = lower_bound(ALL(Rs), ix+1) - Rs.begin() - 1;
int l = SZ(Ls);
for(int a=0, b=SZ(Ls)-1; a<=b; ) {
int m = (a+b) >> 1;
if(Nr[Ls[m]] > Nr[Rs[r]]) l = m, b = m-1; else a = m+1;
}
// printf("right [%d] | [%d]\n", r, l);
int lix = 0;
if(l < SZ(Ls)) lix = Ls[l];
ans += abs(X - lix - 1);
}
return ans;
}
int main() {
cin >> N >> X;
REPO(i, N) scanf("%d", &Nr[i]);
cin >> Q;
REPO(i, N) S.insert(pi(Nr[i], i));
for(int i=X-1; i>=1; i--)
if(Ls.empty() || Nr[Ls.back()] < Nr[i]) Ls.push_back(i);
for(int i=X+1; i<=N; i++)
if(Rs.empty() || Nr[Rs.back()] < Nr[i]) Rs.push_back(i);
REP(q, Q) {
char s[3]; int x, y;
scanf("%s", s); scanf("%d", &x);
if(s[0] == 'F') {
printf("%d\n", getAns(x));
} else {
scanf("%d", &y);
setNr(x, y);
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:96:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
REPO(i, N) scanf("%d", &Nr[i]);
^
cake.cpp:106:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s); scanf("%d", &x);
^
cake.cpp:106:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s); scanf("%d", &x);
^
cake.cpp:110:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &y);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
3200 KB |
Output is correct |
2 |
Correct |
0 ms |
3200 KB |
Output is correct |
3 |
Correct |
0 ms |
3200 KB |
Output is correct |
4 |
Correct |
6 ms |
3200 KB |
Output is correct |
5 |
Correct |
16 ms |
3728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
679 ms |
3596 KB |
Output is correct |
2 |
Correct |
399 ms |
3728 KB |
Output is correct |
3 |
Correct |
496 ms |
3728 KB |
Output is correct |
4 |
Correct |
256 ms |
3728 KB |
Output is correct |
5 |
Correct |
779 ms |
4388 KB |
Output is correct |
6 |
Correct |
659 ms |
4388 KB |
Output is correct |
7 |
Correct |
599 ms |
4388 KB |
Output is correct |
8 |
Correct |
349 ms |
4388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
109 ms |
7952 KB |
Output is correct |
2 |
Correct |
86 ms |
7952 KB |
Output is correct |
3 |
Correct |
73 ms |
7952 KB |
Output is correct |
4 |
Correct |
0 ms |
3200 KB |
Output is correct |
5 |
Correct |
323 ms |
14948 KB |
Output is correct |
6 |
Correct |
346 ms |
14948 KB |
Output is correct |
7 |
Correct |
136 ms |
14948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
3332 KB |
Output is correct |
2 |
Correct |
43 ms |
3464 KB |
Output is correct |
3 |
Correct |
106 ms |
5576 KB |
Output is correct |
4 |
Correct |
139 ms |
5576 KB |
Output is correct |
5 |
Correct |
139 ms |
3332 KB |
Output is correct |
6 |
Correct |
213 ms |
6236 KB |
Output is correct |
7 |
Correct |
193 ms |
3728 KB |
Output is correct |
8 |
Correct |
349 ms |
7952 KB |
Output is correct |
9 |
Correct |
1259 ms |
14948 KB |
Output is correct |
10 |
Correct |
536 ms |
3332 KB |
Output is correct |
11 |
Correct |
739 ms |
4124 KB |
Output is correct |
12 |
Correct |
1146 ms |
12572 KB |
Output is correct |
13 |
Correct |
959 ms |
14948 KB |
Output is correct |