| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 110500 |
2019-05-11T04:08:41 Z |
shoemakerjo |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
72136 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 250010;
const int maxq = 500010;
#define LEFT 0
#define RIGHT 1
#define pii pair<int, int>
int n, q;
int a;
mt19937 mt_rand(time(NULL));
map<int, int> mval; //mamp from index to value
int svals[maxn];
struct node {
node *ch[2];
int indo; //either negative index or query time thing
int we; //the random weight
node *par;
node(int ii) :
indo(ii) {
we = mt_rand() % 1000000000;
ch[0] = ch[1] = NULL;
par = NULL;
}
void setChild(int dir, node *c) {
ch[dir] = c;
// cout << this->indo << " :: " << c->indo << endl;
if (c != NULL) {
c->par = this;
}
}
int getDirection() {
if (par == NULL) return -1;
if (this == par->ch[LEFT]) return LEFT;
if (this == par->ch[RIGHT]) return RIGHT;
return -1;
}
bool isroot() {
return !par || (par->ch[LEFT] != this &&
par->ch[RIGHT] != this);
}
void rotateUp() {
int dir = getDirection();
node *p = par;
if (!p->isroot()) {
p->par->ch[p->getDirection()] = this;
}
par = p->par;
node *pMid = ch[!dir];
p->setChild(dir, pMid);
setChild(!dir, p);
}
};
node *cnodes[maxn]; //current nodes
node *root = NULL;
string tp[maxq];
int qv[maxq][2];
vector<int> inorder;
int seg[maxn*4]; //we want to store a maximum seg tree
void update(int spot, int val, int ss = 1, int se = n, int si = 0) {
if (spot > se || spot < ss || ss > se) return;
if (ss == se) {
seg[si] = val;
return;
}
int mid = (ss+se)/2;
if (spot <= mid) {
update(spot, val, ss, mid, si*2+1);
}
else update(spot, val, mid+1, se, si*2+2);
seg[si] = max(seg[si*2+1], seg[si*2+2]);
}
int query(int qs, int qe, int ss = 1, int se = n, int si = 0) {
if (qs > qe || ss > se || qs > se || qe < ss) return 0;
if (qs <= ss && se <= qe) return seg[si];
int mid = (ss+se)/2;
return max(query(qs, qe, ss, mid, si*2+1),
query(qs, qe, mid+1, se, si*2+2));
}
void buildtree(int ss = 1, int se = n, int si = 0) {
if (ss == se) {
// cout << " here " << ss << " : " << mval[0-ss] << endl;
seg[si] = mval[0-ss];
return;
}
int mid = (ss+se)/2;
buildtree(ss, mid, si*2+1);
buildtree(mid+1, se, si*2+2);
seg[si] = max(seg[si*2+1], seg[si*2+2]);
}
vector<pii> befa;
vector<pii> afta;
void dfs(node *cur) {
// cout << "at: " << cur->indo << endl;
if (cur->ch[LEFT]) {
dfs(cur->ch[LEFT]);
}
inorder.push_back(cur->indo);
if (cur->ch[RIGHT]) {
dfs(cur->ch[RIGHT]);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// srand(time(NULL));
cin >> n >> a;
vector<pii> stuff;
for (int i = 1; i <= n; i++) {
cin >> svals[i];
stuff.push_back(pii(svals[i], i));
}
cin >> q;
sort(stuff.begin(), stuff.end());
reverse(stuff.begin(), stuff.end());
for (pii vp : stuff) {
int ind = vp.second;
node *cur = new node(0-ind);
cnodes[ind] = cur;
if (root == NULL) {
root = cur;
continue;
}
//insert me to be the smallest guy present
node *tmp = root;
while (tmp->ch[LEFT] != NULL) {
tmp = tmp->ch[LEFT];
}
tmp->setChild(LEFT, cur);
//now we need to rotate cur up a bunch
while (!cur->isroot() &&
cur->we > cur->par->we) {
cur->rotateUp();
}
if (cur->isroot()) {
root = cur;
}
}
//store the ten greatest values at any time
vector<int> tg;
for (int i = 0; i < 10 && i < stuff.size(); i++) {
tg.push_back(stuff[i].second);
}
for (int i = 0; i < q; i++) {
// cout << " at start of " << i << " root is: " << root->indo << endl;
cin >> tp[i];
if (tp[i] == "E") {
cin >> qv[i][0] >> qv[i][1];
int ind = qv[i][0];
int ec = qv[i][1];
for (int i = 0; i < tg.size(); i++) {
if (tg[i] == ind) {
tg.erase(tg.begin() + i);
}
}
tg.insert(tg.begin() + ec-1, ind);
node *cur = new node(i);
cnodes[ind] = cur;
if (ec == 1) {
//insert this to be the biggest value we have
node *tmp = root;
while (tmp->ch[RIGHT] != NULL) {
tmp = tmp->ch[RIGHT];
}
tmp->setChild(RIGHT, cur);
}
else {
int aft = tg[ec-2];
//want to be right below this guy
node *tmp = cnodes[aft];
// cout << "THIS: " << tmp->indo << endl;
if (tmp->ch[LEFT] == NULL) {
tmp->setChild(LEFT, cur);
}
else {
tmp = tmp->ch[LEFT];
while (tmp->ch[RIGHT] != NULL) {
tmp = tmp->ch[RIGHT];
}
tmp->setChild(RIGHT, cur);
}
}
while (!cur->isroot() &&
cur->we > cur->par->we) {
cur->rotateUp();
}
if (cur->isroot()) {
root = cur;
}
}
else {
cin >> qv[i][0];
//do not really want to do anything
}
// cout << "done with index: " << i << endl;
}
// vector<int> find;
tg.clear();
for (int i = 0; i < 10 && i < stuff.size(); i++) {
tg.push_back(stuff[i].second);
}
dfs(root);
// cout << "inorder: ";
for (int i = 0; i < inorder.size(); i++) {
int v = inorder[i];
// cout << v << " ";
mval[v] = i+1;
}
// cout << endl;
buildtree();
// cout << "START: " << query(1, n) << endl;
//now we must process the queries
for (int i = a-1; i >= 1; i--) {
if (befa.size() && befa.back().first >= mval[0-i]) {
continue;
}
befa.push_back(pii(mval[0-i], i));
}
befa.push_back(pii(10000000, 0));
for (int i = a+1; i <= n; i++) {
if (afta.size() && afta.back().first >= mval[0-i]) {
continue;
}
afta.push_back(pii(mval[0-i], i));
}
afta.push_back(pii(10000000, n+1));
for (int ii = 0; ii < q; ii++) {
if (tp[ii] == "E") {
int mv = mval[ii];
int cind = qv[ii][0];
update(cind, mv);
if (cind < a) {
//update befa
for (int i = befa.size()-1; i >= 0; i--) {
if (befa[i].second > cind) {
if (befa[i].first < mv) {
befa.insert(befa.begin() + i+1, pii(mv, cind));
}
break; //do not want to do this
}
if (befa[i].first <= mv) {
befa.erase(befa.begin() + i);
}
if (i == 0) {
befa.insert(befa.begin() + 0, pii(mv, cind));
}
}
}
if (cind > a) {
//update afta
for (int i = afta.size()-1; i >= 0; i--) {
if (afta[i].second < cind) {
if (afta[i].first < mv) {
afta.insert(afta.begin() + i+1, pii(mv, cind));
}
break; //do not want to do this
}
if (afta[i].first <= mv) {
afta.erase(afta.begin() + i);
}
if (i == 0) {
afta.insert(afta.begin() + 0, pii(mv, cind));
}
}
}
}
else {
int mq = qv[ii][0];
if (mq == a) {
cout << 0 << '\n';
}
else if (mq < a) {
int bg = query(mq, a-1);
//binary search to find first ind greater than me
int lo = 0, hi = afta.size()-1;
while (lo < hi) {
int mid = (lo + hi)/2;
if (afta[mid].first > bg) {
hi = mid;
}
else lo = mid+1;
}
// if (ii == 0) cout << " value : " << bg << endl;
// if (ii == 0) cout << lo << " : " << befa[lo].second << endl;
int res = afta[lo].second - mq - 1;
cout << res << '\n';
}
else if (mq > a) {
int bg = query(a+1, mq);
int lo = 0, hi = befa.size()-1;
while (lo < hi) {
int mid = (lo + hi)/2;
if (befa[mid].first > bg) {
hi = mid;
}
else lo = mid+1;
}
int res = mq - befa[lo].second - 1;
cout << res << '\n';
}
}
}
cout.flush();
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:175:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < 10 && i < stuff.size(); i++) {
~~^~~~~~~~~~~~~~
cake.cpp:188:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < tg.size(); i++) {
~~^~~~~~~~~~~
cake.cpp:240:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < 10 && i < stuff.size(); i++) {
~~^~~~~~~~~~~~~~
cake.cpp:246:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < inorder.size(); i++) {
~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
15972 KB |
Output is correct |
| 2 |
Correct |
17 ms |
16128 KB |
Output is correct |
| 3 |
Correct |
16 ms |
16000 KB |
Output is correct |
| 4 |
Correct |
22 ms |
16512 KB |
Output is correct |
| 5 |
Correct |
42 ms |
18116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2058 ms |
29792 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2064 ms |
42520 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2037 ms |
30352 KB |
Time limit exceeded |
| 4 |
Correct |
500 ms |
70212 KB |
Output is correct |
| 5 |
Execution timed out |
2028 ms |
26320 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2062 ms |
28632 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2070 ms |
28036 KB |
Time limit exceeded |
| 8 |
Correct |
495 ms |
72136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
219 ms |
30288 KB |
Output is correct |
| 2 |
Correct |
153 ms |
30192 KB |
Output is correct |
| 3 |
Correct |
142 ms |
30200 KB |
Output is correct |
| 4 |
Correct |
17 ms |
16000 KB |
Output is correct |
| 5 |
Correct |
517 ms |
49016 KB |
Output is correct |
| 6 |
Correct |
446 ms |
49000 KB |
Output is correct |
| 7 |
Correct |
264 ms |
48744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
128 ms |
19664 KB |
Output is correct |
| 2 |
Correct |
169 ms |
19832 KB |
Output is correct |
| 3 |
Correct |
691 ms |
27256 KB |
Output is correct |
| 4 |
Correct |
766 ms |
27232 KB |
Output is correct |
| 5 |
Correct |
272 ms |
25328 KB |
Output is correct |
| 6 |
Execution timed out |
2079 ms |
25308 KB |
Time limit exceeded |
| 7 |
Correct |
1362 ms |
29528 KB |
Output is correct |
| 8 |
Execution timed out |
2063 ms |
30040 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2059 ms |
37228 KB |
Time limit exceeded |
| 10 |
Correct |
857 ms |
45972 KB |
Output is correct |
| 11 |
Execution timed out |
2065 ms |
24844 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2060 ms |
34084 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2051 ms |
41060 KB |
Time limit exceeded |
