| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 30146 |
2017-07-22T08:11:22 Z |
cdemirer |
Cake (CEOI14_cake) |
C++14 |
|
1063 ms |
15420 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;
//set<ii> S;
vii topten;
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) {
/*int oldv = seg[a+offset].vmax;
S.erase(mp(oldv, a));
set<ii>::iterator it = S.end();
it--;
for (int i = 0; i < b-1; i++) {
ii q = *it;
set<ii>::iterator it2 = it;
it--;
S.erase(it2);
q.first += 1;
S.insert(q);
change(1, q.second, q.first);
if (q.second < A) lbitmax(A-q.second, q.first);
if (q.second > A) rbitmax(q.second-A, q.first);
}
ii qw;
if (S.size() >= b) {
qw = mp((*it).first+1, a);
}
else {
exit(0);
if (S.size() == 0) qw = mp(1, a);
else {
it = S.begin();
qw = mp((*it).first+1, a);
}
}
S.insert(qw);
change(1, qw.second, qw.first);
if (qw.second < A) lbitmax(A-qw.second, qw.first);
if (qw.second > A) rbitmax(qw.second-A, qw.first);*/
for (int i = 0; i < topten.size(); i++) {
if (topten[i].second == a) {
//cerr << a << endl;
topten.erase(topten.begin()+i);
break;
}
}
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);
}
if (b!=1) topten.insert(topten.begin()+b-1, mp(topten[b-2].first-1, a));
else topten.insert(topten.begin(), mp(topten[0].first+1, a));
//else exit(-1);
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);
topten.resize(min((int)topten.size(), 10));
}
int main(int argc, char **argv) {
//freopen("input", "r", stdin);
//freopen("output", "w", stdout);
//S.insert(mp(0, -1));
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));
//S.insert(mp(seg[i].vmax, i-offset));
topten.pb(mp(seg[i].vmax, i-offset));
}
else seg[i].vmax = 0;
}
sort(topten.begin(), topten.end());
reverse(topten.begin(), topten.end());
topten.resize(min((int)topten.size(), 10));
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);
}
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--;
if (a == A) {
printf("0\n");
}
else if (a > A) {
int m = get(1, A+1, a);
int lp = lbin(m);
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:144:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < topten.size(); i++) {
^
cake.cpp: In function 'int main(int, char**)':
cake.cpp:172: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:178: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:198:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
^
cake.cpp:200:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%c", &t);
^
cake.cpp:202:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%c", &t);
^
cake.cpp:204: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:213: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:233: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 |
0 ms |
12264 KB |
Output is correct |
| 2 |
Correct |
0 ms |
12264 KB |
Output is correct |
| 3 |
Correct |
0 ms |
12264 KB |
Output is correct |
| 4 |
Correct |
6 ms |
12264 KB |
Output is correct |
| 5 |
Correct |
13 ms |
12536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
736 ms |
12536 KB |
Output is correct |
| 2 |
Correct |
416 ms |
12536 KB |
Output is correct |
| 3 |
Correct |
513 ms |
12536 KB |
Output is correct |
| 4 |
Correct |
296 ms |
12536 KB |
Output is correct |
| 5 |
Correct |
663 ms |
12732 KB |
Output is correct |
| 6 |
Correct |
536 ms |
12732 KB |
Output is correct |
| 7 |
Correct |
506 ms |
12732 KB |
Output is correct |
| 8 |
Correct |
349 ms |
12732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
13884 KB |
Output is correct |
| 2 |
Correct |
126 ms |
13884 KB |
Output is correct |
| 3 |
Correct |
83 ms |
13884 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12264 KB |
Output is correct |
| 5 |
Correct |
216 ms |
15420 KB |
Output is correct |
| 6 |
Correct |
193 ms |
15420 KB |
Output is correct |
| 7 |
Correct |
133 ms |
15420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
12404 KB |
Output is correct |
| 2 |
Correct |
43 ms |
12404 KB |
Output is correct |
| 3 |
Correct |
103 ms |
13116 KB |
Output is correct |
| 4 |
Correct |
146 ms |
13116 KB |
Output is correct |
| 5 |
Correct |
179 ms |
12264 KB |
Output is correct |
| 6 |
Correct |
193 ms |
13884 KB |
Output is correct |
| 7 |
Correct |
213 ms |
12536 KB |
Output is correct |
| 8 |
Correct |
259 ms |
13884 KB |
Output is correct |
| 9 |
Correct |
1063 ms |
15420 KB |
Output is correct |
| 10 |
Correct |
573 ms |
12264 KB |
Output is correct |
| 11 |
Correct |
636 ms |
12732 KB |
Output is correct |
| 12 |
Correct |
913 ms |
15420 KB |
Output is correct |
| 13 |
Correct |
896 ms |
15420 KB |
Output is correct |
