Submission #146287

#	Time	Username	Problem	Language	Result	Execution time	Memory
146287		TadijaSebez	Land of the Rainbow Gold (APIO17_rainbow)	C++11	100 / 100	845 ms	149024 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
struct pt{ int x,y;pt(){}pt(int a, int b):x(a),y(b){}};
pt operator - (pt a, pt b){ return pt(a.x-b.x,a.y-b.y);}
bool operator < (pt a, pt b){ return mp(a.x,a.y)<mp(b.x,b.y);}
bool operator == (pt a, pt b){ return mp(a.x,a.y)==mp(b.x,b.y);}
vector<pt> v[4];
void Add(pt p)
{
	v[0].pb(p);
	v[1].pb(p);if(p.x!=1) v[1].pb(p-pt(1,0));
	v[2].pb(p);if(p.y!=1) v[2].pb(p-pt(0,1));
	v[3].pb(p);if(p.x!=1) v[3].pb(p-pt(1,0));if(p.y!=1) v[3].pb(p-pt(0,1));if(min(p.x,p.y)!=1) v[3].pb(p-pt(1,1));
}
void ckmn(int &a, int b){ a=min(a,b);}
void ckmx(int &a, int b){ a=max(a,b);}
const int N=200050;
const int M=900050;
const int H=20*M;
int ls[H],rs[H],tsz,sum[H],n,m,root[4][N];
void Set(int p, int &c, int ss, int se, int qi)
{
	c=++tsz;ls[c]=ls[p];rs[c]=rs[p];sum[c]=sum[p]+1;
	if(ss==se) return;
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[p],ls[c],ss,mid,qi);
	else Set(rs[p],rs[c],mid+1,se,qi);
}
int Get(int p, int c, int ss, int se, int qs, int qe)
{
	if(qs>qe || qs>se || ss>qe) return 0;
	if(qs<=ss && qe>=se) return sum[c]-sum[p];
	int mid=ss+se>>1;
	return Get(ls[p],ls[c],ss,mid,qs,qe)+Get(rs[p],rs[c],mid+1,se,qs,qe);
}
ll Get(int t, int x1, int y1, int x2, int y2){ return (ll)(x2-x1+1)*(y2-y1+1)-Get(root[t][x1-1],root[t][x2],1,N,y1,y2);}
void Build()
{
	for(int i=0;i<4;i++)
	{
		sort(v[i].begin(),v[i].end());
		v[i].resize(unique(v[i].begin(),v[i].end())-v[i].begin());
		for(int j=1,k=0;j<N;j++)
		{
			root[i][j]=root[i][j-1];
			for(;k<v[i].size() && v[i][k].x==j;k++) Set(root[i][j],root[i][j],1,N,v[i][k].y);
		}
	}
}
pt mn,mx;
void init(int R, int C, int sr, int sc, int M, char *S)
{
	n=R,m=C;
	pt pos(sr,sc);
	Add(pos);
	mn=mx=pos;
	for(int i=0;i<M;i++)
	{
		if(S[i]=='N') pos.x--;
		if(S[i]=='S') pos.x++;
		if(S[i]=='W') pos.y--;
		if(S[i]=='E') pos.y++;
		Add(pos);
		ckmn(mn.x,pos.x);ckmn(mn.y,pos.y);
		ckmx(mx.x,pos.x);ckmx(mx.y,pos.y);
	}
	Build();
}
int colour(int x1, int y1, int x2, int y2)
{
	ll ans=Get(0,x1,y1,x2,y2)-Get(1,x1,y1,x2-1,y2)-Get(2,x1,y1,x2,y2-1)+Get(3,x1,y1,x2-1,y2-1);
	if(x1<mn.x && y1<mn.y && x2>mx.x && y2>mx.y) ans++;
	return ans;
}

Compilation message (stderr)

rainbow.cpp: In function 'void Set(int, int&, int, int, int)':
rainbow.cpp:29:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
rainbow.cpp: In function 'int Get(int, int, int, int, int, int)':
rainbow.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
rainbow.cpp: In function 'void Build()':
rainbow.cpp:50:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(;k<v[i].size() && v[i][k].x==j;k++) Set(root[i][j],root[i][j],1,N,v[i][k].y);
         ~^~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26