| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 933134 |
2024-02-25T06:42:58 Z |
Cookie |
Cake (CEOI14_cake) |
C++14 |
|
305 ms |
22604 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 = 250000 + 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[15], 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++){
str.upd(1, 1, n, i, i, tor[i]);
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;
int val = -1;
for(int i = 1; i <= 10; i++){
if(mxid[i] == id){
val = i; break;
}
}
if(val == -1){
for(int j = 10; j >= e + 1; j--){
mxid[j] = mxid[j - 1];
}
mxid[e] = id;
}else{
for(int j = val; j >= e + 1; j--)mxid[j] = mxid[j - 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;
//for(int i = 1; i <= 10; i++)cout << mxid[i] << " ";
//cout << "\n";
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
4 ms |
14816 KB |
Output is correct |
| 5 |
Correct |
9 ms |
14940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
168 ms |
17232 KB |
Output is correct |
| 2 |
Correct |
110 ms |
16980 KB |
Output is correct |
| 3 |
Correct |
166 ms |
17280 KB |
Output is correct |
| 4 |
Correct |
94 ms |
14772 KB |
Output is correct |
| 5 |
Correct |
193 ms |
17488 KB |
Output is correct |
| 6 |
Correct |
164 ms |
17236 KB |
Output is correct |
| 7 |
Correct |
191 ms |
16980 KB |
Output is correct |
| 8 |
Correct |
145 ms |
14684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
15664 KB |
Output is correct |
| 2 |
Correct |
44 ms |
15700 KB |
Output is correct |
| 3 |
Correct |
41 ms |
15700 KB |
Output is correct |
| 4 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
93 ms |
19916 KB |
Output is correct |
| 6 |
Correct |
79 ms |
19792 KB |
Output is correct |
| 7 |
Correct |
73 ms |
19280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
15192 KB |
Output is correct |
| 2 |
Correct |
25 ms |
15196 KB |
Output is correct |
| 3 |
Correct |
43 ms |
15448 KB |
Output is correct |
| 4 |
Correct |
43 ms |
15400 KB |
Output is correct |
| 5 |
Correct |
52 ms |
15812 KB |
Output is correct |
| 6 |
Correct |
70 ms |
15804 KB |
Output is correct |
| 7 |
Correct |
70 ms |
16176 KB |
Output is correct |
| 8 |
Correct |
104 ms |
15956 KB |
Output is correct |
| 9 |
Correct |
305 ms |
22268 KB |
Output is correct |
| 10 |
Correct |
188 ms |
17780 KB |
Output is correct |
| 11 |
Correct |
185 ms |
18108 KB |
Output is correct |
| 12 |
Correct |
282 ms |
22604 KB |
Output is correct |
| 13 |
Correct |
232 ms |
22348 KB |
Output is correct |
