| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 346031 |
2021-01-09T04:02:43 Z |
kym |
Cake (CEOI14_cake) |
C++14 |
|
427 ms |
99752 KB |
#include <bits/stdc++.h>
using namespace std;
#define int ll
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{" << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#else
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
#define reach cerr << "LINE: " << __LINE__ << "\n";
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
typedef tuple<ll,ll,ll,ll> ti4;
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 250005;
int A[MAXN], D[MAXN], n, st;
int qq = 1;
struct node {
int s,e,m,val;
node *l, *r;
node(int _s, int _e){
s=_s,e=_e;
m=(s+e)/2;
val=0;
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void set(int x, int nval) {
if(s==e){
val=nval;
return;
}
if(x>m)r->set(x,nval);
else l->set(x,nval);
val=max(l->val,r->val);
}
void add(int x, int nval) {
if(s==e){
val+=nval;
return;
}
if(x>m)r->add(x,nval);
else l->add(x,nval);
val=max(l->val,r->val);
}
int query(int x, int y) {
if(s==x&&e==y) {
return val;
}
if(x>m)return r->query(x,y);
else if(y<=m)return l->query(x,y);
else return max(l->query(x,m), r->query(m+1,y));
}
} *seg;
int32_t main()
{
IAMSPEED
cin >> n >> st;
seg=new node(0,n);
set<pi,greater<pi>> s;
FOR(i,1,n) {
int x; cin >> x;
x*=2;
//x=n-x+1;
A[i]=x;
seg->set(i,x);
s.insert(pi(x,i));
}
while(s.size()>13)s.erase(prev(s.end()));
int Q; cin >> Q;
while(Q--) {
//dba(A,1,n);
char op; cin >> op;
if(op == 'E') {
int x, e; cin >> x >> e;
int cnt = 1;
auto it = s.begin();
while(cnt < e) {
seg->add(it->s, 1);
A[it->s]++;
pi npair = *it;
s.insert(pi(npair.f+1,npair.s));
it=next(it);
s.erase(prev(it));
it=next(it);
++cnt;
}
int nval = it->f+1;
seg->set(x, nval);
s.erase(s.find(pi(A[x], x)));
s.insert(pi(nval,x));
A[x]=nval;
while(s.size()>13)s.erase(prev(s.end()));
} else {
int x; cin >> x;
if(x==st){
cout << 0 << '\n'; continue;
}
if(x>st){
int mx=seg->query(st+1,x);
int lo = 0, hi = st;
while(lo < hi -1) {
int mid=(lo+hi)/2;
if(seg->query(mid,st-1) > mx)lo=mid;
else hi=mid;
}
cout << x-lo-1 << '\n';
} else {
int mx=seg->query(x,st-1);
//db2(x,st-1);
//db2(seg->query(1,1),seg->query(2,2));
//db(mx);
int lo = st, hi=n+1;
while (lo<hi-1){
int mid=(lo+hi)/2;
if(seg->query(st+1,mid)>mx)hi=mid;
else lo=mid;
}
//db(hi);
cout << hi-x-1 << '\n';
}
}
++qq;
}
}
//g++ -std=c++17 -DLOCAL -Wall -Wshadow -static -O2 -lm -s -w -std=gnu++17 -fmax-errors=512 -o "%e" "%f"
//g++ -std=c++17 -DLOCAL -O2 -Wall -Wl,--stack=268435456 -o "%e" "%f"
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
4076 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
9 ms |
4460 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
10 ms |
4460 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 4 |
Correct |
155 ms |
2284 KB |
Output is correct |
| 5 |
Runtime error |
25 ms |
10476 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
21 ms |
10476 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
24 ms |
10476 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Correct |
173 ms |
5228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
132 ms |
40172 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
87 ms |
40172 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
87 ms |
40172 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Runtime error |
363 ms |
99692 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
364 ms |
99692 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 7 |
Incorrect |
427 ms |
49900 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1772 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
5 ms |
2540 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
55 ms |
20460 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
43 ms |
20332 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
3 ms |
1260 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
75 ms |
26604 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
10 ms |
4460 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
125 ms |
40172 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
391 ms |
99752 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
3 ms |
1260 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
20 ms |
8428 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
280 ms |
79860 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
360 ms |
99564 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
