oj.uz

Submission #132268

# Submission time Handle Problem Language Result Execution time Memory
132268 2019-07-18T15:57:03 Z baluteshih Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1185 ms 420304 KB 
#include "rainbow.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

struct node
{
	int data=0;
	node *l=0,*r=0;
	void up()
	{
		data=0;
		if(l) data+=l->data;
		if(r) data+=r->data;
	}
}*root[400005];

node* modify(int x,int l,int r,node *p,int v)
{
	if(!p) p=new node;
	else p=new node(*p);
	if(l==r)
		return p->data+=v,p;
	int m=l+r>>1;
	if(x<=m) p->l=modify(x,l,m,p->l,v);
	else p->r=modify(x,m+1,r,p->r,v);
	return p->up(),p;
}

node *lch(node *p){return p?p->l:0;}
node *rch(node *p){return p?p->r:0;}
int gdata(node *p){return p?p->data:0;}

int query(int L,int R,int l,int r,node *p,node *q)
{
	if(!p&&!q) return 0;
	if(L<=l && R>=r)
		return gdata(p)-gdata(q);
	int m=l+r>>1;
	if(R<=m) return query(L,R,l,m,lch(p),lch(q));
	if(L>m) return query(L,R,m+1,r,rch(p),rch(q));
	return query(L,R,l,m,lch(p),lch(q))+query(L,R,m+1,r,rch(p),rch(q));
}

int MAXC;
set<pii> s,dt,rl,cl;
int num[256],dx[4]={-1,1,0,0},dy[4]={0,0,1,-1};
vector<pii> wei[400005];

void maintain(int x,int y)
{
	s.insert(MP(x,y));
	dt.insert(MP(x,y)),dt.insert(MP(x+1,y+1)),dt.insert(MP(x+1,y)),dt.insert(MP(x,y+1));
	rl.insert(MP(x,y)),rl.insert(MP(x+1,y));
	cl.insert(MP(x,y)),cl.insert(MP(x,y+1));
}

void init(int R, int C, int sr, int sc, int M, char *S)
{
	num['N']=0,num['S']=1,num['E']=2,num['W']=3,maintain(sr,sc),MAXC=2*C+1;
	for(int i=0;i<M;++i)
		sr+=dx[num[S[i]]],sc+=dy[num[S[i]]],maintain(sr,sc);
	for(auto i:s)
		wei[i.F*2].pb(MP(i.S*2,-1));
	for(auto i:dt)
		wei[i.F*2-1].pb(MP(i.S*2-1,-1));
	for(auto i:rl)
		wei[i.F*2-1].pb(MP(i.S*2,1));
	for(auto i:cl)
		wei[i.F*2].pb(MP(i.S*2-1,1));
	for(int i=1;i<=2*R+1;++i,root[i]=root[i-1])
		for(auto j:wei[i])
			root[i]=modify(j.F,1,MAXC,root[i],j.S);
}

int colour(int ar, int ac, int br, int bc)
{
    return 1+query(ac*2,bc*2,1,MAXC,root[br*2],root[ar*2-1]);
}

Compilation message

rainbow.cpp: In function 'node* modify(int, int, int, node*, int)':
rainbow.cpp:36:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
rainbow.cpp: In function 'int query(int, int, int, int, node*, node*)':
rainbow.cpp:51:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:74:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   sr+=dx[num[S[i]]],sc+=dy[num[S[i]]],maintain(sr,sc);
                  ^
rainbow.cpp:74:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   sr+=dx[num[S[i]]],sc+=dy[num[S[i]]],maintain(sr,sc);
                                    ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10104 KB Output is correct
2 Correct 16 ms 11256 KB Output is correct
3 Incorrect 13 ms 10104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9724 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 728 ms 253656 KB Output is correct
4 Correct 1172 ms 416304 KB Output is correct
5 Correct 1185 ms 412980 KB Output is correct
6 Correct 936 ms 320892 KB Output is correct
7 Correct 987 ms 315608 KB Output is correct
8 Correct 90 ms 13432 KB Output is correct
9 Correct 1159 ms 416316 KB Output is correct
10 Correct 1174 ms 412968 KB Output is correct
11 Correct 949 ms 320772 KB Output is correct
12 Correct 1079 ms 388184 KB Output is correct
13 Correct 1104 ms 416220 KB Output is correct
14 Correct 1131 ms 413248 KB Output is correct
15 Correct 928 ms 321244 KB Output is correct
16 Correct 869 ms 297824 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 1092 ms 415956 KB Output is correct
3 Correct 1012 ms 420304 KB Output is correct
4 Correct 1020 ms 418976 KB Output is correct
5 Correct 779 ms 317276 KB Output is correct
6 Correct 242 ms 88824 KB Output is correct
7 Incorrect 453 ms 164064 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10104 KB Output is correct
2 Correct 16 ms 11256 KB Output is correct
3 Incorrect 13 ms 10104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10104 KB Output is correct
2 Correct 16 ms 11256 KB Output is correct
3 Incorrect 13 ms 10104 KB Output isn't correct
4 Halted 0 ms 0 KB -