제출 #146282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
146282		TadijaSebez	Land of the Rainbow Gold (APIO17_rainbow)	C++11	0 / 100	269 ms	145400 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);v[1].pb(p-pt(1,0));
	v[2].pb(p);v[2].pb(p-pt(0,1));
	v[3].pb(p);v[3].pb(p-pt(1,0));v[3].pb(p-pt(0,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;
struct PersistentSegmentTree
{
	int root[N];
	PersistentSegmentTree(){}
	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);
	}
	void Set(int p, int c, int qi){ Set(root[p],root[c],1,N,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 x1, int y1, int x2, int y2){ return (ll)(x2-x1+1)*(y2-y1+1)-Get(root[x1-1],root[x2],1,N,y1,y2);}
	void Upd(int p, int c){ root[c]=root[p];}
} ST[4];
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++)
		{
			ST[i].Upd(j-1,j);
			for(;k<v[i].size() && v[i][k].x==j;k++) ST[i].Set(j,j,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=ST[0].Get(x1,y1,x2,y2)-ST[1].Get(x1,y1,x2-1,y2)-ST[2].Get(x1,y1,x2,y2-1)+ST[3].Get(x1,y1,x2-1,y2-1);
	if(x1<mn.x && y1<mn.y && x2>mx.x && y2>mx.y) ans++;
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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