| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 49208 |
2018-05-23T18:40:07 Z |
Benq |
Cake (CEOI14_cake) |
C++14 |
|
919 ms |
11436 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
int D[1<<18];
struct {
pair<int,pi> seg[1<<19];
pi query(int x, int ind = 1, int l = 0, int r = (1<<18)-1) {
pi t = {seg[ind].f,seg[ind].s.f*x+seg[ind].s.s};
if (l == r) return t;
int m = (l+r)/2;
if (x <= m) return max(t,query(x,2*ind,l,m));
return max(t,query(x,2*ind+1,m+1,r));
}
void upd(int lo, int hi, pair<int,pi> v, int ind = 1, int l = 0, int r = (1<<18)-1) {
if (r < lo || hi < l) return;
if (lo <= l && r <= hi) {
seg[ind] = v;
return;
}
int m = (l+r)/2;
upd(lo,hi,v,2*ind,l,m);
upd(lo,hi,v,2*ind+1,m+1,r);
}
} Seg;
int N, Q, a;
vpi cur, highest;
int z = 1;
bool contains(pi x, int y) {
return min(x.f,x.s) <= y && y <= max(x.f,x.s);
}
void se(int l, int r, int& t) {
cur.pb({l,r});
if (l <= r) Seg.upd(l,r,{++z,{1,t-l}});
else Seg.upd(r,l,{++z,{-1,t+l}});
t += abs(l-r)+1;
}
void renumerate(int x, int y) {
for (auto& a: highest) if (a.s >= y) a.s ++;
int ind = 0; while (ind < sz(highest) && highest[ind].f < x) ind ++;
highest.insert(highest.begin()+ind,{x,y});
if (ind != sz(highest)-1 && highest[ind+1].f == x) {
int t = highest[ind+1].s;
highest.erase(highest.begin()+ind+1);
for (auto& a: highest) if (a.s > t) a.s --;
}
if (sz(highest) > 10) F0R(i,sz(highest)) if (highest[i].s == 11) highest.erase(highest.begin()+i);
}
void mod(int x, int y) {
renumerate(x,y);
if (x == a) return;
int lo = 0, hi = N-1, t = N;
while (!contains(cur.back(),x)) {
t -= abs(cur.back().f-cur.back().s)+1;
if (cur.back().s < a) lo = cur.back().f+1;
else hi = cur.back().f-1;
cur.pop_back();
}
t -= abs(x-cur.back().s)+1;
if (cur.back().s < a) {
cur.back().s = lo = x+1;
if (cur.back().s > cur.back().f) cur.pop_back();
} else {
cur.back().s = hi = x-1;
if (cur.back().s < cur.back().f) cur.pop_back();
}
int l = sz(highest)-1, r = 0;
while (l >= 0 && highest[l].f >= lo) l --;
while (r < sz(highest) && highest[r].f <= hi) r ++;
if (x == hi+1) {
int LO = ((l == -1) ? 0 : highest[l].f+1);
if (lo > LO) se(lo-1,LO,t);
lo = LO;
} else if (x == lo-1) {
int HI = ((r == sz(highest)) ? N-1 : highest[r].f-1);
if (hi < HI) se(hi+1,HI,t);
hi = HI;
}
while (lo > 0 && hi < N-1) {
if (l == -1) {
se(lo-1,0,t); lo = 0;
} else if (r == sz(highest)) {
se(hi+1,N-1,t); hi = N-1;
} else if (highest[l].s < highest[r].s) {
int HI = ((r+1 == sz(highest)) ? N-1 : highest[r+1].f-1);
se(hi+1,HI,t);
hi = HI; r ++;
} else {
int LO = ((l == 0) ? 0 : highest[l-1].f+1);
se(lo-1,LO,t);
lo = LO; l --;
}
}
if (hi < N-1) se(hi+1,N-1,t);
if (lo > 0) se(lo-1,0,t);
/*for (auto a: cur) cout << a.f << " " << a.s << " | ";
cout << "\n";*/
}
void init() {
int l = a, r = a;
int co = 0;
while (r-l != N-1) {
if (r == N-1 || (l != 0 && D[l-1] < D[r+1])) {
l --; cur.pb({l,l});
Seg.upd(l,l,{1,{0,++co}});
} else {
r ++; cur.pb({r,r});
Seg.upd(r,r,{1,{0,++co}});
}
}
F0R(i,N) if (D[i] > N-10) highest.pb({i,N+1-D[i]});
sort(all(highest));
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> a; a --;
F0R(i,N) {
// D[i] = i+1;
cin >> D[i];
}
// random_shuffle(D,D+N);
cin >> Q;
init();
F0R(i,Q) {
char c; cin >> c;
if (c == 'F') {
int x; cin >> x;
cout << Seg.query(x-1).s << "\n";
} else {
int x, y; cin >> x >> y;
mod(x-1,y);
}
}
}
// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
428 KB |
Output is correct |
| 4 |
Correct |
7 ms |
608 KB |
Output is correct |
| 5 |
Correct |
21 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
443 ms |
1092 KB |
Output is correct |
| 2 |
Correct |
656 ms |
1168 KB |
Output is correct |
| 3 |
Correct |
766 ms |
1168 KB |
Output is correct |
| 4 |
Correct |
574 ms |
1168 KB |
Output is correct |
| 5 |
Correct |
591 ms |
1660 KB |
Output is correct |
| 6 |
Correct |
642 ms |
1660 KB |
Output is correct |
| 7 |
Correct |
919 ms |
1724 KB |
Output is correct |
| 8 |
Correct |
559 ms |
1724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
4336 KB |
Output is correct |
| 2 |
Correct |
81 ms |
4336 KB |
Output is correct |
| 3 |
Correct |
59 ms |
4336 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4336 KB |
Output is correct |
| 5 |
Correct |
149 ms |
8116 KB |
Output is correct |
| 6 |
Correct |
112 ms |
8164 KB |
Output is correct |
| 7 |
Correct |
104 ms |
8164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
8164 KB |
Output is correct |
| 2 |
Correct |
59 ms |
8164 KB |
Output is correct |
| 3 |
Correct |
111 ms |
8164 KB |
Output is correct |
| 4 |
Correct |
106 ms |
8164 KB |
Output is correct |
| 5 |
Correct |
135 ms |
8164 KB |
Output is correct |
| 6 |
Correct |
162 ms |
8164 KB |
Output is correct |
| 7 |
Correct |
182 ms |
8164 KB |
Output is correct |
| 8 |
Correct |
281 ms |
8164 KB |
Output is correct |
| 9 |
Correct |
736 ms |
11324 KB |
Output is correct |
| 10 |
Correct |
444 ms |
11324 KB |
Output is correct |
| 11 |
Correct |
444 ms |
11324 KB |
Output is correct |
| 12 |
Correct |
752 ms |
11324 KB |
Output is correct |
| 13 |
Correct |
515 ms |
11436 KB |
Output is correct |
