| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 454922 |
2021-08-05T10:36:29 Z |
kingfran1907 |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
21884 KB |
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 3e5+10;
const int base = 31337;
const int mod = 1e9+7;
const llint inf = (1LL << 55);
const int logo = 19;
const int off = 1 << logo;
const int treesiz = off << 1;
struct tournament {
llint tour[treesiz];
tournament() {
for (int i = 0; i < treesiz; i++)
tour[i] = inf;
}
void update(int x, llint val) {
x += off;
tour[x] = val;
x /= 2;
while (x > 0) tour[x] = max(tour[x * 2], tour[x * 2 + 1]), x /= 2;
}
llint query(int a, int b, int l, int r, int node) {
if (l > b || r < a) return -inf;
if (l >= a && r <= b) return tour[node];
int mid = (l + r) / 2;
return max(query(a, b, l, mid, node * 2), query(a, b, mid + 1, r, node * 2 + 1));
}
int fin(int l, int r, int node, llint val) {
if (l == r) return l;
int mid = (l + r) / 2;
//printf("looking: (%d %d) %d (%d) --> %lld %lld\n", l, r, node, val, tour[node * 2], tour[node * 2 + 1]);
if (tour[node * 2] < val) return fin(mid + 1, r, node * 2 + 1, val);
return fin(l, mid, node * 2, val);
}
} lef, rig;
int n, q;
int a;
llint niz[maxn];
void update(int x, int val) {
if (x <= a) lef.update(a - x, val);
else rig.update(x - a - 1, val);
}
int main() {
scanf("%d%d", &n, &a); a--;
for (int i = 0; i < n; i++) {
scanf("%lld", niz+i);
}
for (int i = 0; i < n; i++) update(i, niz[i]);
set< pair<llint, int> > s;
for (int i = 0; i < n; i++) {
s.insert(make_pair(-niz[i], i));
while (s.size() > 11) s.erase(--s.end());
}
scanf("%d", &q);
while (q--) {
char type;
scanf(" %c", &type);
if (type == 'E') {
int ind, pos;
scanf("%d%d", &ind, &pos); ind--;
int cnt = pos - 1;
auto iter = s.begin();
while (cnt-- > 0) iter++;
llint val = -(iter->first) + 1;
vector< int > v;
for (iter = s.begin(); iter != s.end(); iter++) v.push_back(iter->second);
s.clear();
llint cp = val;
for (int i = pos - 2; i >= 0; i--) {
int tr = v[i];
niz[tr] = ++cp;
update(tr, niz[tr]);
}
for (int i = 0; i < v.size(); i++) s.insert(make_pair(-niz[v[i]], v[i]));
s.erase(make_pair(-niz[ind], ind));
niz[ind] = val;
s.insert(make_pair(-niz[ind], ind));
update(ind, niz[ind]);
} else {
int x;
scanf("%d", &x); x--;
if (x == a) printf("0\n");
else if (x <= a) {
int sol = a - x;
int maxi = lef.query(0, a - x, 0, off - 1, 1);
int kol = rig.fin(0, off - 1, 1, maxi);
printf("%d\n", sol + kol);
} else {
int sol = x - a - 1;
llint maxi = rig.query(0, x - a - 1, 0, off - 1, 1);
int kol = lef.fin(0, off - 1, 1, maxi);
printf("%d\n", sol + kol);
}
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i = 0; i < v.size(); i++) s.insert(make_pair(-niz[v[i]], v[i]));
| ~~^~~~~~~~~~
cake.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%d%d", &n, &a); a--;
| ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%lld", niz+i);
| ~~~~~^~~~~~~~~~~~~~~
cake.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
cake.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf(" %c", &type);
| ~~~~~^~~~~~~~~~~~~~
cake.cpp:80:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d%d", &ind, &pos); ind--;
| ~~~~~^~~~~~~~~~~~~~~~~~~~
cake.cpp:106:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d", &x); x--;
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
16716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2085 ms |
17356 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2091 ms |
17456 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2087 ms |
17240 KB |
Time limit exceeded |
| 4 |
Correct |
694 ms |
21188 KB |
Output is correct |
| 5 |
Execution timed out |
2071 ms |
17552 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2082 ms |
17616 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2085 ms |
17568 KB |
Time limit exceeded |
| 8 |
Correct |
674 ms |
21884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
93 ms |
19412 KB |
Output isn't correct |
| 2 |
Incorrect |
84 ms |
19336 KB |
Output isn't correct |
| 3 |
Incorrect |
76 ms |
19268 KB |
Output isn't correct |
| 4 |
Incorrect |
9 ms |
16716 KB |
Output isn't correct |
| 5 |
Correct |
134 ms |
21700 KB |
Output is correct |
| 6 |
Incorrect |
126 ms |
21840 KB |
Output isn't correct |
| 7 |
Incorrect |
109 ms |
21576 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2083 ms |
17436 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2073 ms |
17512 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2060 ms |
18240 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2068 ms |
18312 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2065 ms |
17344 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2076 ms |
18236 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2062 ms |
17648 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2089 ms |
18516 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2063 ms |
20984 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2056 ms |
17260 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2044 ms |
17728 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2059 ms |
20140 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2099 ms |
20944 KB |
Time limit exceeded |
