| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 29877 |
2017-07-21T09:58:33 Z |
cdemirer |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
19468 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
typedef struct Node_ {
int llim, rlim;
int vmax;
} Node;
const int segsz = 524288;
const int offset = segsz / 2;
Node seg[segsz];
#define left(x) ((x)*2)
#define right(x) ((x)*2+1)
#define parent(x) ((x)/2)
int get(int x, int l, int r) {
int llim = seg[x].llim;
int rlim = seg[x].rlim;
int mid = (llim + rlim) / 2;
if (l == llim && r == rlim) return seg[x].vmax;
else if (l > mid) return get(right(x), l, r);
else if (r <= mid) return get(left(x), l, r);
else {
int a = get(left(x), l, mid);
int b = get(right(x), mid+1, r);
return max(a, b);
}
}
void refresh(int x) {
x = parent(x);
while (x) {
seg[x].vmax = max(seg[left(x)].vmax, seg[right(x)].vmax);
x = parent(x);
}
}
void change(int x, int p, int u) {
int llim = seg[x].llim;
int rlim = seg[x].rlim;
int mid = (llim + rlim) / 2;
if (llim == rlim) {
seg[x].vmax = u;
refresh(x);
}
else if (p > mid) change(right(x), p, u);
else if (p <= mid) change(left(x), p, u);
else {
cerr << "Impossible branch" << endl;
}
}
int N, A, Q;
vii topten;
int maxcumul[250000];
int lbit[524289], rbit[524289];
int lbitget(int x) {
int mxmm = 0;
while (x > 0) {
mxmm = max(mxmm, lbit[x]);
x -= x & -x;
}
return mxmm;
}
int rbitget(int x) {
int mxmm = 0;
while (x > 0) {
mxmm = max(mxmm, rbit[x]);
x -= x & -x;
}
return mxmm;
}
void lbitmax(int x, int v) {
while (x <= 524388) {
lbit[x] = max(lbit[x], v);
x += x & -x;
}
}
void rbitmax(int x, int v) {
while (x <= 524288) {
rbit[x] = max(rbit[x], v);
x += x & -x;
}
}
int lbin(int w) {
int l = 0, r = A;
while (r > l) {
int mid = (l+r)/2;
if (lbitget(A-mid) > w) l = mid+1;
else r = mid;
}
return l-1;
}
int rbin(int w) {
int l = A, r = N-1;
while (l < r) {
int mid = (l+r+1)/2;
if (rbitget(mid-A) > w) r = mid-1;
else l = mid;
}
return r+1;
}
void addtt(int a, int b) {
bool erased = false;
for (int i = 0; i < topten.size(); i++) {
if (topten[i].second == a) {
topten.erase(topten.begin()+i);
erased = true;
break;
}
}
if (!erased) {
topten.erase(topten.begin()+topten.size()-1);
}
for (int i = 0; i < b-1; i++) {
topten[i].first++;
change(1, topten[i].second, topten[i].first);
if (topten[i].second < A) {
lbitmax(A-topten[i].second, topten[i].first);
}
if (topten[i].second > A) {
rbitmax(topten[i].second-A, topten[i].first);
}
}
int d;
if (b != topten.size()+1) d = topten[b-1].first+1;
else d = topten[b-2].first-1;
topten.insert(topten.begin()+b-1, mp(d, a));
change(1, topten[b-1].second, topten[b-1].first);
if (topten[b-1].second < A) {
lbitmax(A-topten[b-1].second, topten[b-1].first);
}
if (topten[b-1].second > A) {
rbitmax(topten[b-1].second-A, topten[b-1].first);
}
}
int main(int argc, char **argv) {
//freopen("input", "r", stdin);
//freopen("output", "w", stdout);
scanf("%d%d", &N, &A);
A--;
vii arr;
for (int i = offset; i < segsz; i++) {
seg[i].llim = seg[i].rlim = i-offset;
if (i-offset < N) {
scanf("%d", &(seg[i].vmax));
arr.pb(mp(seg[i].vmax, i-offset));
}
else seg[i].vmax = 0;
}
for (int i = offset-1; i > 0; i--) {
seg[i].llim = seg[left(i)].llim;
seg[i].rlim = seg[right(i)].rlim;
seg[i].vmax = max(seg[left(i)].vmax, seg[right(i)].vmax);
}
for (int i = A-1; i >= 0; i--) {
lbitmax(A-i, seg[i+offset].vmax);
}
for (int i = A+1; i < N; i++) {
rbitmax(i-A, seg[i+offset].vmax);
}
/*for (int i = 1; i < N; i++) {
cerr << lbitget(i) << endl;
}*/
sort(arr.begin(), arr.end());
reverse(arr.begin(), arr.end());
for (int i = 0; i < arr.size(); i++) {
topten.pb(arr[i]);
}
scanf("%d", &Q);
char t;
scanf("%c", &t);
while (Q--) {
scanf("%c", &t);
if (t == 'E') {
int a, b; scanf("%d%d", &a, &b);
a--;
addtt(a, b);
/*for (int i = 0; i < N; i++) {
cerr << seg[i+offset].vmax << " ";
}
cerr << endl;*/
}
else if (t == 'F') {
int a; scanf("%d", &a);
a--;
//printf("a: %d\n", a);
if (a == A) {
printf("0\n");
}
else if (a > A) {
int m = get(1, A+1, a);
int lp = lbin(m);
//printf("lp a : %d %d", lp, a);
printf("%d\n", a-lp-1);
}
else {
int m = get(1, a, A-1);
int rp = rbin(m);
printf("%d\n", rp-a-1);
}
}
else {
cerr << "wrong type: " << t << endl;
exit(-1);
}
if (Q) scanf("%c", &t);
}
return 0;
}
Compilation message
cake.cpp: In function 'void addtt(int, int)':
cake.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < topten.size(); i++) {
^
cake.cpp:135:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (b != topten.size()+1) d = topten[b-1].first+1;
^
cake.cpp: In function 'int main(int, char**)':
cake.cpp:179:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < arr.size(); i++) {
^
cake.cpp:152:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &A);
^
cake.cpp:158:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &(seg[i].vmax));
^
cake.cpp:182:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
^
cake.cpp:184:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%c", &t);
^
cake.cpp:186:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%c", &t);
^
cake.cpp:188:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d%d", &a, &b);
^
cake.cpp:197:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a; scanf("%d", &a);
^
cake.cpp:219:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
if (Q) scanf("%c", &t);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
13240 KB |
Output is correct |
| 2 |
Correct |
0 ms |
13240 KB |
Output is correct |
| 3 |
Correct |
0 ms |
13240 KB |
Output is correct |
| 4 |
Correct |
9 ms |
13240 KB |
Output is correct |
| 5 |
Correct |
113 ms |
13580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
13580 KB |
Execution timed out |
| 2 |
Execution timed out |
2000 ms |
13580 KB |
Execution timed out |
| 3 |
Execution timed out |
2000 ms |
13580 KB |
Execution timed out |
| 4 |
Execution timed out |
2000 ms |
13580 KB |
Execution timed out |
| 5 |
Execution timed out |
2000 ms |
14092 KB |
Execution timed out |
| 6 |
Execution timed out |
2000 ms |
14092 KB |
Execution timed out |
| 7 |
Execution timed out |
2000 ms |
14092 KB |
Execution timed out |
| 8 |
Execution timed out |
2000 ms |
14092 KB |
Execution timed out |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
16396 KB |
Output is correct |
| 2 |
Correct |
116 ms |
16396 KB |
Output is correct |
| 3 |
Correct |
106 ms |
16396 KB |
Output is correct |
| 4 |
Correct |
3 ms |
13240 KB |
Output is correct |
| 5 |
Correct |
263 ms |
19468 KB |
Output is correct |
| 6 |
Correct |
263 ms |
19468 KB |
Output is correct |
| 7 |
Correct |
186 ms |
19468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
199 ms |
13380 KB |
Output is correct |
| 2 |
Correct |
266 ms |
13380 KB |
Output is correct |
| 3 |
Execution timed out |
2000 ms |
14860 KB |
Execution timed out |
| 4 |
Execution timed out |
2000 ms |
14860 KB |
Execution timed out |
| 5 |
Correct |
496 ms |
13240 KB |
Output is correct |
| 6 |
Execution timed out |
2000 ms |
16396 KB |
Execution timed out |
| 7 |
Execution timed out |
2000 ms |
13580 KB |
Execution timed out |
| 8 |
Execution timed out |
2000 ms |
16396 KB |
Execution timed out |
| 9 |
Execution timed out |
2000 ms |
19468 KB |
Execution timed out |
| 10 |
Correct |
1409 ms |
13240 KB |
Output is correct |
| 11 |
Execution timed out |
2000 ms |
14092 KB |
Execution timed out |
| 12 |
Execution timed out |
2000 ms |
19468 KB |
Execution timed out |
| 13 |
Execution timed out |
2000 ms |
19468 KB |
Execution timed out |
