| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 697677 |
2023-02-10T17:27:04 Z |
Do_you_copy |
Cake (CEOI14_cake) |
C++17 |
|
908 ms |
18688 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) return max(get(id << 1 | 1, i, j, x, t, mid + 1, r), get(id << 1, i, j, x, t, l, mid));
else return min(get(id << 1, i, j, x, t, l, mid), get(id << 1 | 1, i, j, x, t, mid + 1, r));
}
};
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:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
128 | freopen(taskname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
427 ms |
4692 KB |
Output isn't correct |
| 2 |
Correct |
218 ms |
4736 KB |
Output is correct |
| 3 |
Incorrect |
256 ms |
4732 KB |
Output isn't correct |
| 4 |
Correct |
166 ms |
4732 KB |
Output is correct |
| 5 |
Incorrect |
430 ms |
5472 KB |
Output isn't correct |
| 6 |
Incorrect |
358 ms |
5496 KB |
Output isn't correct |
| 7 |
Incorrect |
275 ms |
5496 KB |
Output isn't correct |
| 8 |
Correct |
184 ms |
5496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
86 ms |
9844 KB |
Output isn't correct |
| 2 |
Incorrect |
66 ms |
9744 KB |
Output isn't correct |
| 3 |
Incorrect |
76 ms |
9708 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
4180 KB |
Output isn't correct |
| 5 |
Incorrect |
190 ms |
17552 KB |
Output isn't correct |
| 6 |
Incorrect |
190 ms |
17724 KB |
Output isn't correct |
| 7 |
Incorrect |
117 ms |
17372 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
4424 KB |
Output isn't correct |
| 2 |
Incorrect |
33 ms |
4544 KB |
Output isn't correct |
| 3 |
Incorrect |
77 ms |
7044 KB |
Output isn't correct |
| 4 |
Incorrect |
94 ms |
6940 KB |
Output isn't correct |
| 5 |
Incorrect |
123 ms |
4556 KB |
Output isn't correct |
| 6 |
Incorrect |
134 ms |
7928 KB |
Output isn't correct |
| 7 |
Incorrect |
117 ms |
5140 KB |
Output isn't correct |
| 8 |
Incorrect |
195 ms |
9316 KB |
Output isn't correct |
| 9 |
Incorrect |
908 ms |
18688 KB |
Output isn't correct |
| 10 |
Incorrect |
392 ms |
5380 KB |
Output isn't correct |
| 11 |
Incorrect |
500 ms |
6708 KB |
Output isn't correct |
| 12 |
Incorrect |
796 ms |
16124 KB |
Output isn't correct |
| 13 |
Incorrect |
605 ms |
18652 KB |
Output isn't correct |
