| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 346029 |
2021-01-09T04:00:30 Z |
kym |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
57396 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));
}
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));
s.erase(it);
it=s.lower_bound(pi(npair.f+1,npair.s));
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;
} 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 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
8 ms |
620 KB |
Output is correct |
| 5 |
Correct |
27 ms |
2540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
640 ms |
6652 KB |
Output is correct |
| 2 |
Correct |
312 ms |
6764 KB |
Output is correct |
| 3 |
Correct |
414 ms |
6764 KB |
Output is correct |
| 4 |
Correct |
232 ms |
6764 KB |
Output is correct |
| 5 |
Correct |
759 ms |
9964 KB |
Output is correct |
| 6 |
Correct |
578 ms |
10348 KB |
Output is correct |
| 7 |
Correct |
478 ms |
10092 KB |
Output is correct |
| 8 |
Correct |
279 ms |
10604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
418 ms |
21996 KB |
Output is correct |
| 2 |
Correct |
267 ms |
21868 KB |
Output is correct |
| 3 |
Correct |
272 ms |
21740 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
664 ms |
52460 KB |
Output is correct |
| 6 |
Correct |
623 ms |
52460 KB |
Output is correct |
| 7 |
Correct |
387 ms |
52204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
1516 KB |
Output is correct |
| 2 |
Correct |
73 ms |
1900 KB |
Output is correct |
| 3 |
Correct |
259 ms |
11244 KB |
Output is correct |
| 4 |
Correct |
277 ms |
11276 KB |
Output is correct |
| 5 |
Correct |
226 ms |
2156 KB |
Output is correct |
| 6 |
Correct |
538 ms |
15372 KB |
Output is correct |
| 7 |
Correct |
299 ms |
4588 KB |
Output is correct |
| 8 |
Correct |
359 ms |
22464 KB |
Output is correct |
| 9 |
Execution timed out |
2088 ms |
56140 KB |
Time limit exceeded |
| 10 |
Correct |
749 ms |
5740 KB |
Output is correct |
| 11 |
Correct |
1201 ms |
9964 KB |
Output is correct |
| 12 |
Execution timed out |
2070 ms |
46428 KB |
Time limit exceeded |
| 13 |
Correct |
1902 ms |
57396 KB |
Output is correct |
