| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 160496 |
2019-10-28T02:25:39 Z |
luciocf |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
29648 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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};
}
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+1;
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)
{
ll 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:126: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:139:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < mx.size(); i++)
~~^~~~~~~~~~~
cake.cpp:148:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < mx.size(); i++)
~~^~~~~~~~~~~
cake.cpp:164:9: warning: unused variable 'p' [-Wunused-variable]
int p = pos[M], last = findR(1, 1, n, A+1, M);
^
cake.cpp:174:9: warning: unused variable 'p' [-Wunused-variable]
int p = pos[M], last = findL(1, 1, n, A-1, M);
^
cake.cpp:94: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:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
cake.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
cake.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &op);
~~~~~^~~~~~~~~~~~
cake.cpp:117: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:158: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 |
376 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 |
1955 ms |
28668 KB |
Output isn't correct |
| 2 |
Correct |
1880 ms |
28792 KB |
Output is correct |
| 3 |
Correct |
1915 ms |
28656 KB |
Output is correct |
| 4 |
Correct |
1896 ms |
28648 KB |
Output is correct |
| 5 |
Execution timed out |
2060 ms |
29304 KB |
Time limit exceeded |
| 6 |
Correct |
1978 ms |
29536 KB |
Output is correct |
| 7 |
Execution timed out |
2019 ms |
29440 KB |
Time limit exceeded |
| 8 |
Correct |
1990 ms |
29648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
4508 KB |
Output is correct |
| 2 |
Correct |
91 ms |
4344 KB |
Output is correct |
| 3 |
Correct |
83 ms |
4344 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Correct |
142 ms |
8444 KB |
Output is correct |
| 6 |
Incorrect |
167 ms |
8568 KB |
Output isn't correct |
| 7 |
Correct |
121 ms |
8220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
2172 KB |
Output isn't correct |
| 2 |
Correct |
94 ms |
2428 KB |
Output is correct |
| 3 |
Correct |
184 ms |
4344 KB |
Output is correct |
| 4 |
Correct |
193 ms |
4396 KB |
Output is correct |
| 5 |
Incorrect |
321 ms |
5384 KB |
Output isn't correct |
| 6 |
Correct |
379 ms |
7416 KB |
Output is correct |
| 7 |
Correct |
436 ms |
7416 KB |
Output is correct |
| 8 |
Correct |
862 ms |
14456 KB |
Output is correct |
| 9 |
Incorrect |
1568 ms |
25288 KB |
Output isn't correct |
| 10 |
Incorrect |
1153 ms |
17020 KB |
Output isn't correct |
| 11 |
Correct |
1451 ms |
18424 KB |
Output is correct |
| 12 |
Correct |
1604 ms |
24132 KB |
Output is correct |
| 13 |
Incorrect |
1431 ms |
25400 KB |
Output isn't correct |
