| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 369242 | YJU | Land of the Rainbow Gold (APIO17_rainbow) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e5+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
struct Segment_Tree{
struct node{
ll sum;
node *lc,*rc;
node(){sum=0;lc=rc=0;}
}*rt=new node();
ll get(node *nd){
return (nd?nd->sum:0);
}
void _ins(node *nd,ll l,ll r,ll to,ll del){
if(l==r-1){nd->sum+=del;return ;}
ll mid=(l+r)>>1;
if(to<mid){
if(!nd->lc)nd->lc=new node();
_ins(nd->lc,l,mid,to,del);
}else{
if(!nd->rc)nd->rc=new node();
_ins(nd->rc,mid,r,to,del);
}
nd->sum=get(nd->lc)+get(nd->rc);
}
ll _ask(node *nd,ll l,ll r,ll ql,ll qr){
if(l>=ql&&r<=qr)return get(nd);
if(l>=qr||r<=ql)return 0;
ll mid=(l+r)>>1;
return (nd->lc?_ask(nd->lc,l,mid,ql,qr):0LL)+(nd->rc?_ask(nd->rc,mid,r,ql,qr):0LL);
}
ll ask(ll ql,ll qr){
return _ask(rt,0,N,ql,qr);
}
void ins(ll to,ll del){
_ins(rt,0,N,to,del);
}
}seg[4][4*N];
void ins(ll sid,ll id,ll l,ll r,ll tox,ll toy,ll del){
seg[sid][id].ins(toy,del);
if(l==r-1)return ;
ll mid=(l+r)>>1;
if(tox<mid){
ins(sid,id*2,l,mid,tox,toy,del);
}else{
ins(sid,id*2+1,mid,r,tox,toy,del);
}
}
ll query(ll sid,ll id,ll l,ll r,ll fl,ll fr,ll bl,ll br){
if(l>=fl&&r<=fr){return seg[sid][id].ask(bl,br);}
if(l>=fr||r<=fl)return 0;
ll mid=(l+r)>>1;
return query(sid,id*2,l,mid,fl,fr,bl,br)+query(sid,id*2+1,mid,r,fl,fr,bl,br);
}
//for [ar,br] [ac,bc]
//sid=0 V : [ar,br] [ac,bc]
//sid=1 VE : [ar,br) [ac,bc]
//sid=2 HE : [ar,br] [ac,bc)
//sid=3 F : [ar,br) [ac,bc)
ll mir,mxr,mic,mxc;
void init(ll R,ll C,ll sr,ll sc,ll M,string S){
vector<pll> v[4];
mic=mxc=sc;
mir=mxr=sr;
for(int i=0;i<=M;i++){
mic=min(mic,sc);mxc=max(mxc,sc);
mir=min(mir,sr);mxr=max(mxr,sr);
v[0].pb(mp(sr,sc));
v[1].pb(mp(sr,sc));v[1].pb(mp(sr-1,sc));
v[2].pb(mp(sr,sc));v[2].pb(mp(sr,sc-1));
v[3].pb(mp(sr,sc));v[3].pb(mp(sr-1,sc));v[3].pb(mp(sr,sc-1));v[3].pb(mp(sr-1,sc-1));
//
if(i==M)break;
if(S[i]=='N')--sr;
if(S[i]=='S')++sr;
if(S[i]=='W')--sc;
if(S[i]=='E')++sc;
}
//unique
for(int i=0;i<4;i++)sort(v[i].begin(),v[i].end()),v[i].erase(unique(v[i].begin(),v[i].end()),v[i].end());
//
for(int sid=0;sid<4;sid++){
for(auto i:v[sid]){
ins(sid,1,0,N,i.X,i.Y,-1);
}
}
}
ll colours(ll ar,ll ac,ll br,ll bc){
ll ans=(br-ar+1)*(bc-ac+1)-(br-ar)*(bc-ac+1)-(br-ar+1)*(bc-ac)+(br-ar)*(bc-ac);
ans+=query(0,1,0,N,ar,br+1,ac,bc+1);
ans-=query(1,1,0,N,ar,br,ac,bc+1);
ans-=query(2,1,0,N,ar,br+1,ac,bc);
ans+=query(3,1,0,N,ar,br,ac,bc);
ans+=(mxc<bc&&mic>ac&&mxr<br&&mir>ar?1:0);
return ans;
}
/*
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
init(6,4,3,3,9,"NWESSWEWS");
cout<<colours(2,3,2,3)<<"\n";
cout<<colours(3,2,4,4)<<"\n";
cout<<colours(5,3,6,4)<<"\n";
cout<<colours(1,2,5,3)<<"\n";
return 0;
}
//*/