| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 697691 |
2023-02-10T18:02:14 Z |
Do_you_copy |
Cake (CEOI14_cake) |
C++17 |
|
2000 ms |
22028 KB |
//Then
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 250004 + 1;
//const int Mod = 1e9 + 7;
//const int inf =
int n, A;
int a[maxN];
bool found;
struct TST{
int st[maxN * 4];
TST(){
memset(st, 0, sizeof(st));
}
void update(int id, int i, int x, int l, int r){
if (l == r){
st[id] = x;
return;
}
int mid = (l + r) >> 1;
if (i <= mid) update(id << 1, i, x, l, mid);
else update(id << 1 | 1, i, x, mid + 1, r);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int getmax(int id, int i, int j, int l, int r){
if (i > r || l > j) return 0;
if (i <= l && r <= j) return st[id];
int mid = (l + r) >> 1;
return max(getmax(id << 1, i, j, l, mid), getmax(id << 1 | 1, i, j, mid + 1, r));
}
int find(int id, int i, int j, int x, int t, int l, int r){
if (l == r) return l;
int mid = (l + r) >> 1;
if (t){
if (st[id << 1 | 1] > x) return find(id << 1 | 1, i, j, x, t, mid + 1, r);
else return find(id << 1, i, j, x, t, l, mid);
}
else{
if (st[id << 1] > x) return find(id << 1, i, j, x, t, l, mid);
else return find(id << 1 | 1, i, j, x, t, mid + 1, r);
}
}
int get(int id, int i, int j, int x, bool t, int l, int r){
if (i > r || l > j) return t ? 0 : n + 1;
cerr << i << " " << j << " " << t << " " << l << " " << r << "\n";
if (i <= l && r <= j){
if (st[id] < x || found) return t ? 0 : n + 1;
found = 1;
return find(id, i, j, x, t, l, r);
}
if (st[id] < x || found) return t ? 0 : n + 1;
int mid = (l + r) >> 1;
if (t){
int fi = get(id << 1 | 1, i, j, x, t, mid + 1, r);
int se = get(id << 1, i, j, x, t, l, mid);
return max(fi, se);
}
else{
int fi = get(id << 1, i, j, x, t, l, mid);
int se = get(id << 1 | 1, i, j, x, t, mid + 1, r);
return min(fi, se);
}
}
};
TST st;
void Init(){
cin >> n >> A;
set <pii, greater <pii>> S;
for (int i = 1; i <= n; ++i){
cin >> a[i];
S.insert({a[i], i});
}
for (int i = 1; i <= n; ++i){
st.update(1, i, a[i], 1, n);
}
int q; cin >> q;
int cur = n;
while (q--){
char c;
int i, e; cin >> c;
if (c == 'E'){
cin >> i >> e;
S.erase(S.find(make_pair(a[i], i)));
++cur;
a[i] = cur - e + 1;
st.update(1, i, a[i], 1, n);
vector <int> V;
while (--e){
V.pb(S.begin()->se);
S.erase(S.begin());
}
for (int j: V){
++a[j];
st.update(1, j, a[j], 1, n);
}
S.insert(make_pair(a[i], i));
for (int j: V) S.insert(make_pair(a[j], j));
}
else{
cin >> i;
found = 0;
if (i > A){
int maxx = st.getmax(1, A + 1, i, 1, n);
int pos = st.get(1, 1, A - 1, maxx, 1, 1, n);
cout << i - pos - 1<< "\n";
}
else if (i < A){
int maxx = st.getmax(1, i, A - 1, 1, n);
int pos = st.get(1, A + 1, n, maxx, 0, 1, n);
cout << pos - i - 1<< "\n";
}
else{
cout << 0 << "\n";
}
}
}
}
#define debug
#define taskname "test"
signed main(){
faster
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
int tt = 1;
//cin >> tt;
while (tt--){
Init();
}
if (fopen("timeout.txt", "r")){
ofstream timeout("timeout.txt");
timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
timeout.close();
#ifndef debug
cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
#endif // debug
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
136 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | freopen(taskname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4180 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
4256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
402 ms |
4704 KB |
Output isn't correct |
| 2 |
Correct |
246 ms |
4916 KB |
Output is correct |
| 3 |
Correct |
270 ms |
4748 KB |
Output is correct |
| 4 |
Correct |
206 ms |
4776 KB |
Output is correct |
| 5 |
Incorrect |
462 ms |
5524 KB |
Output isn't correct |
| 6 |
Correct |
435 ms |
5628 KB |
Output is correct |
| 7 |
Correct |
299 ms |
5520 KB |
Output is correct |
| 8 |
Correct |
236 ms |
5596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2052 ms |
13844 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2093 ms |
14016 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2065 ms |
14220 KB |
Time limit exceeded |
| 4 |
Incorrect |
2 ms |
4180 KB |
Output isn't correct |
| 5 |
Execution timed out |
2096 ms |
21288 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2060 ms |
21448 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2096 ms |
22028 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1958 ms |
7696 KB |
Output isn't correct |
| 2 |
Correct |
1938 ms |
7904 KB |
Output is correct |
| 3 |
Execution timed out |
2090 ms |
10712 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2033 ms |
10496 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2033 ms |
7228 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2094 ms |
11760 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2085 ms |
8376 KB |
Time limit exceeded |
| 8 |
Correct |
280 ms |
9420 KB |
Output is correct |
| 9 |
Execution timed out |
2083 ms |
20992 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2087 ms |
7364 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2098 ms |
8888 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2100 ms |
18228 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2061 ms |
21088 KB |
Time limit exceeded |
