| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 697696 |
2023-02-10T18:21:03 Z |
Do_you_copy |
Cake (CEOI14_cake) |
C++17 |
|
888 ms |
18600 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;
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;
while (q--){
char c;
int i, e; cin >> c;
if (c == 'E'){
cin >> i >> e;
S.erase(S.find(make_pair(a[i], i)));
vector <int> V;
while (--e){
V.pb(S.begin()->se);
S.erase(S.begin());
}
int cnt = S.size() ? S.begin()->fi : 0;
V.pb(i);
reverse(V.begin(), V.end());
for (int j: V){
a[j] = ++cnt;
st.update(1, j, a[j], 1, n);
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:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | freopen(taskname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 4 |
Correct |
5 ms |
4308 KB |
Output is correct |
| 5 |
Correct |
14 ms |
4692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
421 ms |
4692 KB |
Output is correct |
| 2 |
Correct |
237 ms |
4764 KB |
Output is correct |
| 3 |
Correct |
258 ms |
4736 KB |
Output is correct |
| 4 |
Correct |
162 ms |
4692 KB |
Output is correct |
| 5 |
Correct |
433 ms |
5468 KB |
Output is correct |
| 6 |
Correct |
357 ms |
5580 KB |
Output is correct |
| 7 |
Correct |
301 ms |
5500 KB |
Output is correct |
| 8 |
Correct |
205 ms |
5500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
9848 KB |
Output is correct |
| 2 |
Correct |
74 ms |
9700 KB |
Output is correct |
| 3 |
Correct |
69 ms |
9624 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 5 |
Correct |
210 ms |
17520 KB |
Output is correct |
| 6 |
Correct |
189 ms |
17612 KB |
Output is correct |
| 7 |
Correct |
120 ms |
17280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
4416 KB |
Output is correct |
| 2 |
Correct |
32 ms |
4564 KB |
Output is correct |
| 3 |
Correct |
84 ms |
6948 KB |
Output is correct |
| 4 |
Correct |
89 ms |
6992 KB |
Output is correct |
| 5 |
Correct |
116 ms |
4556 KB |
Output is correct |
| 6 |
Correct |
142 ms |
8064 KB |
Output is correct |
| 7 |
Correct |
120 ms |
5216 KB |
Output is correct |
| 8 |
Correct |
183 ms |
9332 KB |
Output is correct |
| 9 |
Correct |
888 ms |
18580 KB |
Output is correct |
| 10 |
Correct |
379 ms |
5384 KB |
Output is correct |
| 11 |
Correct |
500 ms |
6528 KB |
Output is correct |
| 12 |
Correct |
826 ms |
15904 KB |
Output is correct |
| 13 |
Correct |
601 ms |
18600 KB |
Output is correct |
