| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 933113 |
2024-02-25T06:08:53 Z |
Cookie |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
30556 KB |
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
const ll mod =1e9 + 7;
const int mxn = 2e5 + 5, mxq = 1e5 + 5, sq = 300, mxv = 1e4 + 5;
//const int base = (1 <<18);
const ll inf = 3e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!
// <3;
struct ST{
int st[4 * mxn + 1], lz[4 * mxn + 1];
void init(){
for(int i = 1; i <= 4 * mxn; i++)lz[i] = -1;
}
void push(int nd){
int &v = lz[nd];
if(v == -1)return;
lz[nd << 1] = lz[nd << 1 | 1] = st[nd << 1] = st[nd << 1 | 1] = v;
v = -1;
}
void upd(int nd, int l, int r, int ql, int qr, int v){
if(ql > r || qr < l)return;
if(ql <= l && qr >= r){
lz[nd] = st[nd] = v;
return;
}
int mid = (l + r) >> 1;
push(nd);
upd(nd << 1, l, mid, ql, qr, v); upd(nd << 1 | 1, mid + 1, r, ql, qr, v);
}
int get(int nd, int l, int r, int id){
if(l == r)return(st[nd]);
int mid = (l + r) >> 1;
push(nd);
if(id <= mid)return(get(nd << 1, l, mid, id));
else return(get(nd << 1 | 1, mid + 1, r, id));
}
};
ST stl, str;
int n, a, q;
int mxid[11], d[mxn + 1], tol[mxn + 1], tor[mxn + 1];
void solve(){
cin >> n >> a;
for(int i = 1; i <= n; i++){
cin >> d[i];
if(n + 1 - d[i] <= 10){
mxid[n + 1 - d[i]] = i;
}
}
int lp = a, rp = a;
tol[a] = tor[a] = a;
while(lp != 1 || rp != n){
if(lp == 1){
rp++; tol[rp] = lp;
}else if(rp == n){
lp--; tor[lp] = rp;
}else if(d[lp - 1] < d[rp + 1]){
lp--; tor[lp] = rp;
}else{
rp++; tol[rp] = lp;
}
}
stl.init(); str.init();
cin >> q;
mxid[11] = n + 1;
for(int i = 1; i <= n; i++){
if(i <= a)str.upd(1, 1, n, i, i, tor[i]);
else stl.upd(1, 1, n, i, i, tol[i]);
}
while(q--){
char c; cin >> c;
if(c == 'F'){
int id; cin >> id;
if(id <= a){
int idr = str.get(1, 1, n, id);
cout << idr - id << "\n";
}else{
int idl = stl.get(1, 1, n, id);
cout << id - idl << "\n";
}
}else{
int id, e; cin >> id >> e;
for(int i = e + 1; i <= min(n, 10); i++){
mxid[i] = mxid[i - 1];
}
mxid[e] = id;
if(id == a)continue;
bool sign = (id > a);
int atl, atr, atv = e;
if(sign)atl = stl.get(1, 1, n, id - 1) - 1, atr = id;
else atr = str.get(1, 1, n, id + 1) + 1, atl = id;
while(1){
if(sign == 0){
// ->
int idmn = 11, mnv = n + 1;
for(int j = atv - 1; j >= 1; j--){
if(mxid[j] >= atr && mxid[j] < mnv){
idmn = j; mnv = mxid[j];
}
}
stl.upd(1, 1, n, atr, mnv - 1, atl + 1);
atr = mnv; atv = idmn;
if(atr == n + 1){
str.upd(1, 1, n, 1, atl, n);
break;
}
}else{
//<-
int idmx = 11, mxv = 0;
for(int j = atv - 1; j >= 1; j--){
if(mxid[j] <= atl && mxid[j] > mxv){
idmx = j; mxv = mxid[j];
}
}
str.upd(1, 1, n, mxv + 1, atl, atr - 1);
atl = mxv; atv = idmx;
if(atl == 0){
stl.upd(1, 1, n, atr, n, 1);
break;
}
}
sign = !sign;
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("SODOCLA.INP", "r", stdin);
//freopen("SODOCLA.INP", "w", stdout);
int tt; tt = 1;
while(tt--){
solve();
}
return(0);
}
/*
10 5
2 3 4 5 6
*/
Compilation message
cake.cpp: In function 'void solve()':
cake.cpp:86:12: warning: array subscript 11 is above array bounds of 'int [11]' [-Warray-bounds]
86 | mxid[11] = n + 1;
| ~~~~~~~^
cake.cpp:61:5: note: while referencing 'mxid'
61 | int mxid[11], d[mxn + 1], tol[mxn + 1], tor[mxn + 1];
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
14940 KB |
Output isn't correct |
| 2 |
Incorrect |
5 ms |
14960 KB |
Output isn't correct |
| 3 |
Incorrect |
7 ms |
15196 KB |
Output isn't correct |
| 4 |
Incorrect |
5 ms |
14940 KB |
Output isn't correct |
| 5 |
Incorrect |
15 ms |
15196 KB |
Output isn't correct |
| 6 |
Incorrect |
14 ms |
15216 KB |
Output isn't correct |
| 7 |
Incorrect |
14 ms |
15196 KB |
Output isn't correct |
| 8 |
Incorrect |
11 ms |
15196 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
16464 KB |
Output isn't correct |
| 2 |
Incorrect |
35 ms |
15700 KB |
Output isn't correct |
| 3 |
Incorrect |
32 ms |
15704 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
14940 KB |
Output isn't correct |
| 5 |
Execution timed out |
2067 ms |
15196 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2044 ms |
15196 KB |
Time limit exceeded |
| 7 |
Runtime error |
26 ms |
30556 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
15192 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
15192 KB |
Output isn't correct |
| 3 |
Incorrect |
28 ms |
15448 KB |
Output isn't correct |
| 4 |
Incorrect |
29 ms |
15764 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 6 |
Incorrect |
35 ms |
15880 KB |
Output isn't correct |
| 7 |
Incorrect |
6 ms |
15176 KB |
Output isn't correct |
| 8 |
Incorrect |
58 ms |
16336 KB |
Output isn't correct |
| 9 |
Runtime error |
33 ms |
30544 KB |
Execution killed with signal 11 |
| 10 |
Incorrect |
3 ms |
15192 KB |
Output isn't correct |
| 11 |
Incorrect |
11 ms |
15196 KB |
Output isn't correct |
| 12 |
Incorrect |
121 ms |
17632 KB |
Output isn't correct |
| 13 |
Execution timed out |
2090 ms |
15312 KB |
Time limit exceeded |
