| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 140630 |
2019-08-03T22:13:32 Z |
silxikys |
Cake (CEOI14_cake) |
C++14 |
|
1692 ms |
44780 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*
* fast queries (few updates):
* after each update, simply recompute all orders and
* queries in O(1)
*
* fast updates (few queries):
* Give everyone enough space initally (5e5,2*5e5,3*5e5,...,10*5e5,10*5e5+1)
* Save each update, then before each query, recompute all orders and
* answer the query.
*/
const int maxn = 250005;
const int maxq = 5e5+5;
const ll INF = 1LL<<62;
int N, Q;
int d[maxn];
ll a[maxn];
struct Node {
int s, e, m;
//covers s,e;
ll sum;
ll mini;
ll maxi;
Node *l, *r;
Node(int a, int b) {
s = a;
e = b;
sum = INF;
mini = INF;
maxi = INF;
if (s != e) {
m = (s+e)/2;
l = new Node(s,m);
r = new Node(m+1,e);
}
else {
l = NULL;
r = NULL;
}
}
void add(int i, ll x) {
if (s == e) {
sum = x;
mini = sum;
maxi = sum;
return;
}
if (i <= m) {
l->add(i,x);
}
else if (i > m) {
r->add(i,x);
}
else assert(false);
sum = l->sum + r->sum;
mini = min(l->mini,r->mini);
maxi = max(l->maxi,r->maxi);
}
ll getmini(int st, int en) {
if (st <= s && e <= en) {
return mini;
}
ll ret = INF;
if (st <= m) {
ret = min(ret,l->getmini(st,en));
}
if (en > m) {
ret = min(ret,r->getmini(st,en));
}
return ret;
}
ll getmaxi(int st, int en) {
if (st <= s && e <= en) {
return maxi;
}
ll ret = 0;
if (st <= m) {
ret = max(ret,l->getmaxi(st,en));
}
if (en > m) {
ret = max(ret,r->getmaxi(st,en));
}
return ret;
}
};
int start;
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> N >> start;
vector<pair<int,int>> ps;
for (int i = 1; i <= N; i++) {
cin >> d[i];
ps.push_back({d[i],i});
}
sort(ps.begin(),ps.end(),greater<pair<int,int>>());
int t = 1;
multiset<ll> ms;
Node *root = new Node(1,N);
for (auto p: ps) {
a[p.second] = 1LL*t*maxq;
root->add(p.second,a[p.second]);
if (t <= 10) ms.insert(a[p.second]);
t++;
}
/*
for (int i = 1; i <= N; i++) {
cout << i << ": " << root->getmini(i,i) << '\n';
}
*/
cin >> Q;
while (Q--) {
char c; cin >> c;
if (c == 'E') { //update
int i, e; cin >> i >> e;
ll ai = -1;
int j = 1;
for (auto it = ms.begin(); it != ms.end(); ++it, j++) {
if (j == e) {
//found it
ai = *it-Q;
/*
cout << "found " << ai << '\n';
cout << *it << '\n';
*/
break;
}
}
if (ms.count(a[i])) {
ms.erase(a[i]);
}
else ms.erase(prev(ms.end()));
a[i] = ai;
ms.insert(ai);
root->add(i,a[i]);
/*
for (int i = 1; i <= N; i++) {
cout << i << ": " << root->getmini(i,i) << '\n';
}
cout << '\n';
*/
}
else { //query
int b; cin >> b;
if (b == start) {
cout << 0 << '\n';
}
else if (b < start) {
int c = start+1;
int mn = root->getmini(b,start);
for (int k = 17; k >= 0; k--) {
int nc = c+(1<<k);
if (nc > N) continue;
if (root->getmini(start+1,nc) > mn) {
c = nc;
}
}
int d = root->getmini(start+1,c) > mn ? c : start;
//cout << b << ' ' << d << '\n';
cout << (d-b) << '\n';
}
else {
int c = start-1;
int mn = root->getmini(start,b);
for (int k = 17; k >= 0; k--) {
int nc = c-(1<<k);
if (nc < 1) continue;
if (root->getmini(nc,start-1) > mn) {
c = nc;
}
}
int d = root->getmini(c,start-1) > mn ? c : start;
//cout << d << ' ' << b << '\n';
cout << (b-d) << '\n';
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
6136 KB |
Output isn't correct |
| 2 |
Incorrect |
188 ms |
6268 KB |
Output isn't correct |
| 3 |
Incorrect |
211 ms |
6264 KB |
Output isn't correct |
| 4 |
Incorrect |
199 ms |
6264 KB |
Output isn't correct |
| 5 |
Incorrect |
262 ms |
8556 KB |
Output isn't correct |
| 6 |
Incorrect |
234 ms |
9004 KB |
Output isn't correct |
| 7 |
Incorrect |
238 ms |
8740 KB |
Output isn't correct |
| 8 |
Incorrect |
219 ms |
9080 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
483 ms |
16860 KB |
Output isn't correct |
| 2 |
Incorrect |
319 ms |
16880 KB |
Output isn't correct |
| 3 |
Incorrect |
294 ms |
16632 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 5 |
Incorrect |
703 ms |
39724 KB |
Output isn't correct |
| 6 |
Incorrect |
664 ms |
39656 KB |
Output isn't correct |
| 7 |
Incorrect |
429 ms |
39604 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
1272 KB |
Output isn't correct |
| 2 |
Incorrect |
73 ms |
1616 KB |
Output isn't correct |
| 3 |
Incorrect |
223 ms |
8856 KB |
Output isn't correct |
| 4 |
Incorrect |
187 ms |
8792 KB |
Output isn't correct |
| 5 |
Incorrect |
148 ms |
2028 KB |
Output isn't correct |
| 6 |
Incorrect |
474 ms |
12108 KB |
Output isn't correct |
| 7 |
Incorrect |
252 ms |
3960 KB |
Output isn't correct |
| 8 |
Incorrect |
225 ms |
17392 KB |
Output isn't correct |
| 9 |
Incorrect |
1618 ms |
44416 KB |
Output isn't correct |
| 10 |
Incorrect |
420 ms |
5316 KB |
Output isn't correct |
| 11 |
Incorrect |
769 ms |
8824 KB |
Output isn't correct |
| 12 |
Incorrect |
1507 ms |
36732 KB |
Output isn't correct |
| 13 |
Incorrect |
1692 ms |
44780 KB |
Output isn't correct |
