| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 49205 |
2018-05-23T17:21:50 Z |
Benq |
Cake (CEOI14_cake) |
C++14 |
|
742 ms |
13572 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(l,r,{++z,{-1,t+r}});
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().s+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();
}
/*for (auto a: cur) cout << a.f << " " << a.s << " | ";
cout << "\n----\n";*/
int l = sz(highest)-1, r = 0;
while (l >= 0 && highest[l].f >= lo) l --;
while (r < sz(highest) && highest[r].f <= hi) r ++;
while (l != -1 || r != sz(highest)) {
if (l == -1 || (r != sz(highest) && 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 --;
}
}
/*for (auto a: cur) cout << a.f << " " << a.s << " | ";
cout << "\n----\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) cin >> D[i];
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 |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
5 ms |
744 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
643 ms |
1840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
204 ms |
1856 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
22 ms |
1860 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Incorrect |
687 ms |
1964 KB |
Output isn't correct |
| 5 |
Runtime error |
11 ms |
2484 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
10 ms |
2484 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
10 ms |
2484 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Incorrect |
742 ms |
2576 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
68 ms |
6592 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
57 ms |
6592 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
107 ms |
6592 KB |
Output isn't correct |
| 4 |
Correct |
3 ms |
6592 KB |
Output is correct |
| 5 |
Incorrect |
138 ms |
10632 KB |
Output isn't correct |
| 6 |
Runtime error |
141 ms |
13404 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Incorrect |
102 ms |
13556 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
13556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
31 ms |
13556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
18 ms |
13556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
21 ms |
13556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
12 ms |
13556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
21 ms |
13556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
30 ms |
13556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
31 ms |
13556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
74 ms |
13556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
13 ms |
13556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
9 ms |
13556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
68 ms |
13556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
75 ms |
13572 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
