| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 160497 |
2019-10-28T04:08:44 Z |
luciocf |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
31224 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
int n;
int a[maxn];
pair<int, int> aux[maxn];
map<int, int> pos;
int tree[4*maxn];
vector<pair<int, int>> mx;
void faz(void)
{
sort(aux+1, aux+n+1);
for (int i = max(1, n-12); i <= n; i++)
mx.push_back({a[aux[i].second], aux[i].second});
}
void build(int node, int l, int r)
{
if (l == r)
{
tree[node] = a[l];
return;
}
int mid = (l+r)>>1;
build(2*node, l, mid); build(2*node+1, mid+1, r);
tree[node] = max(tree[2*node], tree[2*node+1]);
}
void upd(int node, int l, int r, int pos, int v)
{
if (l == r)
{
tree[node] = v;
return;
}
int mid = (l+r)>>1;
if (pos <= mid) upd(2*node, l, mid, pos, v);
else upd(2*node+1, mid+1, r, pos, v);
tree[node] = max(tree[2*node], tree[2*node+1]);
}
int query(int node, int l, int r, int a, int b)
{
if (l > b || r < a) return -1;
if (l >= a && r <= b) return tree[node];
int mid = (l+r)>>1;
return max(query(2*node, l, mid, a, b), query(2*node+1, mid+1, r, a, b));
}
int findL(int node, int l, int r, int pos, int v)
{
if (l > pos || tree[node] <= v) return -1;
if (l == r) return l;
int mid = (l+r)>>1;
int p1 = findL(2*node+1, mid+1, r, pos, v);
return (p1 == -1 ? findL(2*node, l, mid, pos, v) : p1);
}
int findR(int node, int l, int r, int pos, int v)
{
if (r < pos || tree[node] <= v) return -1;
if (l == r) return l;
int mid = (l+r)>>1;
int p1 = findR(2*node, l, mid, pos, v);
return (p1 == -1 ? findR(2*node+1, mid+1, r, pos, v) : p1);
}
int main(void)
{
int A;
scanf("%d %d", &n, &A);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
aux[i] = {a[i], i}, pos[a[i]] = i;
}
faz();
build(1, 1, n);
int q;
scanf("%d", &q);
for (int t = 1; t <= q; t++)
{
char op;
scanf(" %c", &op);
if (op == 'E')
{
int ind, e;
scanf("%d %d", &ind, &e);
vector<pair<int, int>> aux;
a[ind] = mx[mx.size()-e].first;
pos[a[ind]] = ind;
int qtd = 0;
for (int i = mx.size()-1; i > mx.size()-e; i--, qtd++)
aux.push_back(mx[i]);
aux.push_back({a[ind], ind}), ++qtd;
for (int i = mx.size()-e; i >= 0 && qtd < 13; i--, qtd++)
aux.push_back(mx[i]);
mx.clear();
for (int i = aux.size()-1; i >= 0; i--)
mx.push_back(aux[i]);
for (int i = 1; i < mx.size(); i++)
{
if (mx[i].first == mx[i-1].first)
{
a[mx[i].second]++;
mx[i].first++;
}
}
for (int i = 0; i < mx.size(); i++)
{
upd(1, 1, n, mx[i].second, mx[i].first);
pos[mx[i].first] = mx[i].second;
}
}
else
{
int ind;
scanf("%d", &ind);
if (ind == A) printf("0\n");
else if (ind < A)
{
int M = query(1, 1, n, ind, A-1);
int p = pos[M], last = findR(1, 1, n, A+1, M);
if (last == -1)
printf("%d\n", n-ind);
else
printf("%d\n", last-ind-1);
}
else
{
int M = query(1, 1, n, A+1, ind);
int p = pos[M], last = findL(1, 1, n, A-1, M);
if (last == -1)
printf("%d\n", ind-1);
else
printf("%d\n", ind-last-1);
}
}
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:124:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = mx.size()-1; i > mx.size()-e; i--, qtd++)
~~^~~~~~~~~~~~~
cake.cpp:137:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < mx.size(); i++)
~~^~~~~~~~~~~
cake.cpp:146:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < mx.size(); i++)
~~^~~~~~~~~~~
cake.cpp:162:9: warning: unused variable 'p' [-Wunused-variable]
int p = pos[M], last = findR(1, 1, n, A+1, M);
^
cake.cpp:172:9: warning: unused variable 'p' [-Wunused-variable]
int p = pos[M], last = findL(1, 1, n, A-1, M);
^
cake.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &A);
~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
cake.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
cake.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &op);
~~~~~^~~~~~~~~~~~
cake.cpp:115:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &ind, &e);
~~~~~^~~~~~~~~~~~~~~~~~~
cake.cpp:156:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &ind);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1957 ms |
25320 KB |
Output isn't correct |
| 2 |
Correct |
1913 ms |
25336 KB |
Output is correct |
| 3 |
Correct |
1953 ms |
25464 KB |
Output is correct |
| 4 |
Execution timed out |
2051 ms |
25388 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2076 ms |
26332 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2043 ms |
26352 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2031 ms |
26144 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2032 ms |
26388 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
8312 KB |
Output is correct |
| 2 |
Correct |
146 ms |
8184 KB |
Output is correct |
| 3 |
Correct |
140 ms |
8200 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Correct |
357 ms |
18404 KB |
Output is correct |
| 6 |
Incorrect |
351 ms |
18420 KB |
Output isn't correct |
| 7 |
Correct |
223 ms |
18168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
2240 KB |
Output isn't correct |
| 2 |
Correct |
97 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
207 ms |
6264 KB |
Output is correct |
| 4 |
Correct |
239 ms |
6280 KB |
Output is correct |
| 5 |
Incorrect |
309 ms |
4952 KB |
Output isn't correct |
| 6 |
Correct |
416 ms |
9292 KB |
Output is correct |
| 7 |
Correct |
451 ms |
6872 KB |
Output is correct |
| 8 |
Correct |
914 ms |
17164 KB |
Output is correct |
| 9 |
Incorrect |
1771 ms |
31128 KB |
Output isn't correct |
| 10 |
Incorrect |
1169 ms |
14072 KB |
Output isn't correct |
| 11 |
Correct |
1257 ms |
15632 KB |
Output is correct |
| 12 |
Correct |
1675 ms |
28124 KB |
Output is correct |
| 13 |
Incorrect |
1665 ms |
31224 KB |
Output isn't correct |
