| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 30817 |
2017-07-27T04:38:39 Z |
zscoder |
Cake (CEOI14_cake) |
C++14 |
|
766 ms |
29100 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef tree<ll,null_type,greater<ll>,rb_tree_tag,tree_order_statistics_node_update> pbds;
int a[250001];
int query[511111];
int tmpidx[511111];
int st[1000001];
bool used[250001];
vector<pair<char,pair<int,int> > > queries;
void build(int id, int l, int r)
{
if(r-l<2)
{
st[id]=a[l];
return ;
}
int mid=(l+r)>>1;
build(id*2,l,mid);
build(id*2+1,mid,r);
st[id]=max(st[id*2],st[id*2+1]);
}
void update(int id, int l, int r, int pos, int v)
{
if(pos>=r||pos<l) return ;
if(r-l<2)
{
st[id]=v;
return ;
}
int mid=(l+r)>>1;
update(id*2,l,mid,pos,v);
update(id*2+1,mid,r,pos,v);
st[id]=max(st[id*2],st[id*2+1]);
}
int querymax(int id, int l, int r, int ql, int qr)
{
if(ql>=r||l>=qr) return -1;
//cerr<<id<<' '<<l<<' '<<r<<' '<<ql<<' '<<qr<<' '<<st[id]<<'\n';
if(ql<=l&&r<=qr) return st[id];
int mid=(l+r)>>1;
return max(querymax(id*2,l,mid,ql,qr),querymax(id*2+1,mid,r,ql,qr));
}
int queryr(int id, int l, int r, int ql, int qr, int v)
{
if(ql>=r||l>=qr) return -1;
if(r-l<2)
{
//cerr<<id<<' '<<l<<' '<<r<<' '<<ql<<' '<<qr<<' '<<v<<' '<<st[id]<<'\n';
if(st[id]>=v) return l;
else return -1;
}
int mid=(l+r)>>1;
if(ql<=l&&r<=qr)
{
//cerr<<id<<' '<<l<<' '<<r<<' '<<ql<<' '<<qr<<' '<<v<<' '<<st[id*2+1]<<'\n';
if(st[id*2+1]>=v)
{
return queryr(id*2+1,mid,r,ql,qr,v);
}
else
{
return queryr(id*2,l,mid,ql,qr,v);
}
}
return max(queryr(id*2,l,mid,ql,qr,v),queryr(id*2+1,mid,r,ql,qr,v));
}
int queryl(int id, int l, int r, int ql, int qr, int v)
{
if(ql>=r||l>=qr) return 100000000;
if(r-l<2)
{
if(st[id]>=v) return l;
else return 100000000;
}
int mid=(l+r)>>1;
if(ql<=l&&r<=qr)
{
if(st[id*2]>=v)
{
return queryl(id*2,l,mid,ql,qr,v);
}
else
{
return queryl(id*2+1,mid,r,ql,qr,v);
}
}
return min(queryl(id*2,l,mid,ql,qr,v),queryl(id*2+1,mid,r,ql,qr,v));
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n,s;
cin>>n>>s;
s--;
for(int i=0;i<n;i++)
{
cin>>a[i];
a[i]--;
}
int q; cin>>q;
int upd=0;
for(int i=0;i<q;i++)
{
char c; int pos;
cin>>c>>pos;
pos--;
if(c=='E')
{
int v; cin>>v;
v--;
tmpidx[i]=v;
queries.pb(mp(c,mp(pos,v)));
}
else
{
queries.pb(mp(c,mp(pos,-1)));
}
}
build(1,0,n);
set<pair<int,int> > cur;
for(int i=0;i<n;i++) cur.insert(mp(-a[i],i));
//freopen("cake.out","w",stdout);
for(int i = 0; i < q; i++)
{
char c = queries[i].fi;
int pos = queries[i].se.fi;
int v = queries[i].se.se;
if(c=='E')
{
cur.erase(mp(-a[pos],pos));
vector<ii> hold;
int num = n + upd;
for(int i = 0; i < v; i++)
{
ii tmp = (*cur.begin());
cur.erase(cur.begin());
tmp.fi=-num;
a[tmp.se]=num;
update(1,0,n,tmp.se,num);
hold.pb(tmp);
num--;
}
update(1,0,n,pos,num);
a[pos]=num;
hold.pb(mp(-num,pos));
for(int i=0;i<hold.size();i++) cur.insert(hold[i]);
/*
vi vec;
for(int j=0;j<n;j++) vec.pb(a[j]);
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
reverse(vec.begin(),vec.end());
assert(vec.size()==n);
if(vec[tmpidx[i]]!=a[pos])
{
cerr<<tmpidx[i]<<' '<<v<<'\n';
for(int j=0;j<n;j++)
{
cerr<<a[j]<<' ';
}
cerr<<'\n';
return 0;
}
*/
upd++;
}
else
{
if(s==pos)
{
cout<<0<<'\n';
}
else if(s>pos)
{
int tmp = querymax(1,0,n,pos,s);
int ridx = queryl(1,0,n,s+1,n,tmp);
if(ridx>n) ridx=n;
ridx--;
//[pos+1,ridx];
//cerr<<"L : "<<s<<' '<<pos<<' '<<tmp<<' '<<ridx<<'\n';
cout<<ridx-pos<<'\n';
}
else
{
int tmp = querymax(1,0,n,s+1,pos+1);
int lidx = queryr(1,0,n,0,s,tmp);
//[lidx+1,pos-1];
//cerr<<"R : "<<s<<' '<<pos<<' '<<tmp<<' '<<lidx<<'\n';
cout<<pos-1-lidx<<'\n';
}
}
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:166:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<hold.size();i++) cur.insert(hold[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
11304 KB |
Output is correct |
| 2 |
Correct |
0 ms |
11304 KB |
Output is correct |
| 3 |
Correct |
0 ms |
11304 KB |
Output is correct |
| 4 |
Runtime error |
3 ms |
11528 KB |
Execution killed because of forbidden syscall writev (20) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
743 ms |
20560 KB |
Output is correct |
| 2 |
Correct |
419 ms |
20560 KB |
Output is correct |
| 3 |
Correct |
549 ms |
20560 KB |
Output is correct |
| 4 |
Correct |
299 ms |
20560 KB |
Output is correct |
| 5 |
Correct |
766 ms |
20560 KB |
Output is correct |
| 6 |
Correct |
679 ms |
20560 KB |
Output is correct |
| 7 |
Correct |
476 ms |
20560 KB |
Output is correct |
| 8 |
Correct |
329 ms |
20560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
17496 KB |
Execution killed because of forbidden syscall writev (20) |
| 2 |
Runtime error |
46 ms |
17496 KB |
Execution killed because of forbidden syscall writev (20) |
| 3 |
Runtime error |
49 ms |
17496 KB |
Execution killed because of forbidden syscall writev (20) |
| 4 |
Correct |
0 ms |
11304 KB |
Output is correct |
| 5 |
Runtime error |
233 ms |
24492 KB |
Execution killed because of forbidden syscall writev (20) |
| 6 |
Runtime error |
156 ms |
24492 KB |
Execution killed because of forbidden syscall writev (20) |
| 7 |
Runtime error |
106 ms |
24492 KB |
Execution killed because of forbidden syscall writev (20) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
12496 KB |
Execution killed because of forbidden syscall writev (20) |
| 2 |
Runtime error |
13 ms |
12496 KB |
Execution killed because of forbidden syscall writev (20) |
| 3 |
Runtime error |
46 ms |
15120 KB |
Execution killed because of forbidden syscall writev (20) |
| 4 |
Runtime error |
39 ms |
15120 KB |
Execution killed because of forbidden syscall writev (20) |
| 5 |
Runtime error |
43 ms |
15952 KB |
Execution killed because of forbidden syscall writev (20) |
| 6 |
Runtime error |
59 ms |
17448 KB |
Execution killed because of forbidden syscall writev (20) |
| 7 |
Runtime error |
39 ms |
15952 KB |
Execution killed because of forbidden syscall writev (20) |
| 8 |
Runtime error |
283 ms |
19032 KB |
Execution killed because of forbidden syscall writev (20) |
| 9 |
Runtime error |
353 ms |
29100 KB |
Execution killed because of forbidden syscall writev (20) |
| 10 |
Runtime error |
103 ms |
20560 KB |
Execution killed because of forbidden syscall writev (20) |
| 11 |
Runtime error |
103 ms |
20560 KB |
Execution killed because of forbidden syscall writev (20) |
| 12 |
Runtime error |
196 ms |
26856 KB |
Execution killed because of forbidden syscall writev (20) |
| 13 |
Runtime error |
306 ms |
29100 KB |
Execution killed because of forbidden syscall writev (20) |
