oj.uz

Submission #369246

# Submission time Handle Problem Language Result Execution time Memory
369246 2021-02-21T02:06:21 Z YJU Land of the Rainbow Gold (APIO17_rainbow) C++14
47 / 100
 3000 ms 641400 KB 
#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)

int mir,mxr,mic,mxc;

void init(int R,int C,int sr,int sc,int M,char *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);
		}
	}
}

int colour(int ar,int ac,int br,int 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;
}
//*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 125932 KB Output is correct
2 Correct 154 ms 127084 KB Output is correct
3 Correct 147 ms 126316 KB Output is correct
4 Correct 150 ms 126464 KB Output is correct
5 Correct 157 ms 127232 KB Output is correct
6 Correct 136 ms 125676 KB Output is correct
7 Correct 136 ms 125676 KB Output is correct
8 Correct 139 ms 125676 KB Output is correct
9 Correct 180 ms 125676 KB Output is correct
10 Correct 169 ms 125676 KB Output is correct
11 Correct 148 ms 126316 KB Output is correct
12 Correct 154 ms 126700 KB Output is correct
13 Correct 173 ms 127340 KB Output is correct
14 Correct 167 ms 127816 KB Output is correct
15 Correct 139 ms 125676 KB Output is correct
16 Correct 144 ms 125604 KB Output is correct
17 Correct 161 ms 125676 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 125604 KB Output is correct
2 Correct 161 ms 125676 KB Output is correct
3 Correct 1809 ms 425476 KB Output is correct
4 Correct 2835 ms 620952 KB Output is correct
5 Correct 2872 ms 586216 KB Output is correct
6 Correct 1988 ms 395376 KB Output is correct
7 Correct 2095 ms 395336 KB Output is correct
8 Correct 349 ms 142076 KB Output is correct
9 Correct 2845 ms 620664 KB Output is correct
10 Correct 2838 ms 586208 KB Output is correct
11 Correct 2040 ms 395596 KB Output is correct
12 Correct 2413 ms 593132 KB Output is correct
13 Correct 2638 ms 620704 KB Output is correct
14 Correct 2620 ms 586056 KB Output is correct
15 Correct 1994 ms 395376 KB Output is correct
16 Correct 2074 ms 480880 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 125676 KB Output is correct
2 Correct 2471 ms 641028 KB Output is correct
3 Correct 2011 ms 616240 KB Output is correct
4 Correct 2434 ms 623732 KB Output is correct
5 Correct 1665 ms 492068 KB Output is correct
6 Correct 525 ms 159472 KB Output is correct
7 Correct 831 ms 175500 KB Output is correct
8 Correct 1985 ms 389572 KB Output is correct
9 Correct 1809 ms 342296 KB Output is correct
10 Correct 523 ms 158084 KB Output is correct
11 Correct 1252 ms 299824 KB Output is correct
12 Correct 2445 ms 641100 KB Output is correct
13 Correct 2005 ms 616076 KB Output is correct
14 Correct 2382 ms 623656 KB Output is correct
15 Correct 1662 ms 492092 KB Output is correct
16 Correct 448 ms 155632 KB Output is correct
17 Correct 828 ms 176240 KB Output is correct
18 Correct 1751 ms 230860 KB Output is correct
19 Correct 2226 ms 621968 KB Output is correct
20 Correct 2283 ms 615200 KB Output is correct
21 Correct 1950 ms 389488 KB Output is correct
22 Correct 1841 ms 342156 KB Output is correct
23 Correct 528 ms 158212 KB Output is correct
24 Correct 1239 ms 299856 KB Output is correct
25 Correct 2419 ms 641400 KB Output is correct
26 Correct 2008 ms 615956 KB Output is correct
27 Correct 2453 ms 623772 KB Output is correct
28 Correct 1659 ms 492144 KB Output is correct
29 Correct 450 ms 155632 KB Output is correct
30 Correct 846 ms 176240 KB Output is correct
31 Correct 1746 ms 231152 KB Output is correct
32 Correct 2252 ms 621936 KB Output is correct
33 Correct 2256 ms 615260 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 125932 KB Output is correct
2 Correct 154 ms 127084 KB Output is correct
3 Correct 147 ms 126316 KB Output is correct
4 Correct 150 ms 126464 KB Output is correct
5 Correct 157 ms 127232 KB Output is correct
6 Correct 136 ms 125676 KB Output is correct
7 Correct 136 ms 125676 KB Output is correct
8 Correct 139 ms 125676 KB Output is correct
9 Correct 180 ms 125676 KB Output is correct
10 Correct 169 ms 125676 KB Output is correct
11 Correct 148 ms 126316 KB Output is correct
12 Correct 154 ms 126700 KB Output is correct
13 Correct 173 ms 127340 KB Output is correct
14 Correct 167 ms 127816 KB Output is correct
15 Correct 139 ms 125676 KB Output is correct
16 Correct 144 ms 125604 KB Output is correct
17 Correct 161 ms 125676 KB Output is correct
18 Execution timed out 3101 ms 232588 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 125932 KB Output is correct
2 Correct 154 ms 127084 KB Output is correct
3 Correct 147 ms 126316 KB Output is correct
4 Correct 150 ms 126464 KB Output is correct
5 Correct 157 ms 127232 KB Output is correct
6 Correct 136 ms 125676 KB Output is correct
7 Correct 136 ms 125676 KB Output is correct
8 Correct 139 ms 125676 KB Output is correct
9 Correct 180 ms 125676 KB Output is correct
10 Correct 169 ms 125676 KB Output is correct
11 Correct 148 ms 126316 KB Output is correct
12 Correct 154 ms 126700 KB Output is correct
13 Correct 173 ms 127340 KB Output is correct
14 Correct 167 ms 127816 KB Output is correct
15 Correct 139 ms 125676 KB Output is correct
16 Correct 144 ms 125604 KB Output is correct
17 Correct 161 ms 125676 KB Output is correct
18 Execution timed out 3101 ms 232588 KB Time limit exceeded
19 Halted 0 ms 0 KB -