| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 25983 |
2017-06-25T10:00:06 Z |
윤교준(#1090) |
Cake (CEOI14_cake) |
C++11 |
|
1083 ms |
6028 KB |
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MAXN (250005)
#define MAXQ (500005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
const int MX = 262144;
struct SEG {
int d[MX*2];
void upd(int x, int r) { for(x += MX, d[x] = r, x /= 2; x; x /= 2) d[x] = max(d[x*2], d[x*2+1]); }
int get(int s, int e) {
int r = 0; for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
if(s&1) upmax(r, d[s++]); if(~e&1) upmax(r, d[e--]);
} return r;
}
};
SEG seg;
set<pii> V;
int A[MAXN], P[MAXN];
int BQ[15];
int N, T, Q, K;
void upf(int idx, int e) {
int ret = -1;
for(int i = 1; i <= K; i++) if(BQ[i] == idx) { ret = i; break; }
if(-1 != ret) for(int i = ret-1; e <= i; i--) BQ[i+1] = BQ[i];
else for(int i = K-1; e <= i; i--) BQ[i+1] = BQ[i];
BQ[e] = idx; A[idx] = A[BQ[e+1]];
for(int i = 1; i <= e; i++) A[BQ[i]]++;
for(int i = 1; i <= 10; i++) seg.upd(BQ[i], A[BQ[i]]);
}
set<pii>::iterator sf(int idx) {
auto ret = lower_bound(allv(V), (pii){idx, INF});
ret--; return ret;
}
int gl(int s, int e, int x) {
if(e < s || seg.get(s, e) <= x) return -1;
if(s == e) return s;
const int m = (s+e)/2;
const int ret = gl(s, m, x);
return -1 == ret ? gl(m+1, e, x) : ret;
}
int gr(int s, int e, int x) {
if(e < s || seg.get(s, e) <= x) return -1;
if(s == e) return s;
const int m = (s+e)/2;
const int ret = gl(m+1, e, x);
return -1 == ret ? gl(s, m, x) : ret;
}
int main() {
scanf("%d%d", &N, &T); K = min(10, N);
for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
for(int i = 1; i <= N; i++) seg.upd(i, A[i]);
for(int i = 1; i <= N; i++) P[i] = i;
sort(P+1, P+N+1, [&](const int& a, const int& b) -> bool { return A[a] > A[b]; });
for(int i = 1, S = 1, E = N; i <= N; i++) {
int idx = P[i]; if(idx == T) continue;
if(idx < T) {
if(idx < S) continue;
V.insert({S, idx});
S = idx + 1;
} else {
if(E < idx) continue;
V.insert({idx, E});
E = idx - 1;
}
}
for(int i = 1; i <= N; i++) if(N-K+1 <= A[i]) BQ[N-A[i]+1] = i;
for(scanf("%d", &Q); Q--;) {
char c; int x, y; scanf(" %c%d", &c, &x);
if('E' == c) {
scanf("%d", &y);
if(x == T) continue;
auto it = sf(x); upf(x, y);
if(x < T) {
if(A[x] < A[(*it).second]) continue;
vector<pii> VV;
while(A[(*it).second] <= A[x]) {
VV.pb(*it);
if(V.begin() == it) break;
it--;
}
for(pii& v : VV) V.erase(v);
if(VV[0].second != x) V.insert({x+1, VV[0].second});
V.insert({VV.back().first, x});
} else {
if(A[x] < A[(*it).first]) continue;
vector<pii> VV;
while(A[(*it).first] <= A[x]) {
VV.pb(*it); it++;
if(V.end() == it) break;
}
for(pii& v : VV) V.erase(v);
if(VV[0].first != x) V.insert({VV[0].first, x-1});
V.insert({x, VV.back().second});
}
} else {
if(x == T) { puts("0"); continue; }
pii ret = *sf(x);
if(ret.second < T) {
const int idx = gl(T+1, N, seg.get(ret.second, T-1));
printf("%d\n", -1 == idx ? N-x : idx-x-1);
} else {
const int idx = gr(1, T-1, seg.get(T+1, ret.first));
printf("%d\n", -1 == idx ? x-1 : x-idx-1);
}
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:83:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &T); K = min(10, N);
^
cake.cpp:84:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
^
cake.cpp:101:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(scanf("%d", &Q); Q--;) {
^
cake.cpp:102:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
char c; int x, y; scanf(" %c%d", &c, &x);
^
cake.cpp:104: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 |
6028 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
6028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
643 ms |
6028 KB |
Output isn't correct |
| 2 |
Correct |
593 ms |
6028 KB |
Output is correct |
| 3 |
Incorrect |
669 ms |
6028 KB |
Output isn't correct |
| 4 |
Correct |
569 ms |
6028 KB |
Output is correct |
| 5 |
Incorrect |
769 ms |
6028 KB |
Output isn't correct |
| 6 |
Incorrect |
593 ms |
6028 KB |
Output isn't correct |
| 7 |
Incorrect |
659 ms |
6028 KB |
Output isn't correct |
| 8 |
Correct |
576 ms |
6028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
159 ms |
6028 KB |
Output isn't correct |
| 2 |
Incorrect |
99 ms |
6028 KB |
Output isn't correct |
| 3 |
Incorrect |
106 ms |
6028 KB |
Output isn't correct |
| 4 |
Correct |
0 ms |
6028 KB |
Output is correct |
| 5 |
Incorrect |
213 ms |
6028 KB |
Output isn't correct |
| 6 |
Incorrect |
213 ms |
6028 KB |
Output isn't correct |
| 7 |
Incorrect |
176 ms |
6028 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
6028 KB |
Output isn't correct |
| 2 |
Incorrect |
69 ms |
6028 KB |
Output isn't correct |
| 3 |
Incorrect |
136 ms |
6028 KB |
Output isn't correct |
| 4 |
Incorrect |
119 ms |
6028 KB |
Output isn't correct |
| 5 |
Incorrect |
209 ms |
6028 KB |
Output isn't correct |
| 6 |
Incorrect |
219 ms |
6028 KB |
Output isn't correct |
| 7 |
Incorrect |
216 ms |
6028 KB |
Output isn't correct |
| 8 |
Incorrect |
323 ms |
6028 KB |
Output isn't correct |
| 9 |
Incorrect |
1016 ms |
6028 KB |
Output isn't correct |
| 10 |
Incorrect |
593 ms |
6028 KB |
Output isn't correct |
| 11 |
Incorrect |
613 ms |
6028 KB |
Output isn't correct |
| 12 |
Incorrect |
1083 ms |
6028 KB |
Output isn't correct |
| 13 |
Incorrect |
799 ms |
6028 KB |
Output isn't correct |
