제출 #105408

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105408		puyu_liao	무지개나라 (APIO17_rainbow)	C++14	12 / 100	1802 ms	180060 KiB

rainbow

#include<bits/stdc++.h>
#include<stdint.h>
using namespace std;
#define IOS {cin.tie(0);ios_base::sync_with_stdio(false);}
#define N 200005
#define lowbit(x) (x&-x)
#include"rainbow.h"
struct dbit{
	unordered_map<int,int> mp[N];
	int n,m;
	void init(int _n,int _m){
		n = _n,m = _m;
		for(int i=1;i<=n;i++) mp[i].clear();
	}
	void add(int x,int y,int c){
		for(;x<=n;x+=lowbit(x)) for(int j=y;j<=m;j+=lowbit(j))
			mp[x][j] += c;
	}
	int qur(int x,int y){
		int r = 0;
		for(;x;x-=lowbit(x)) for(int j=y;j;j-=lowbit(j)){
			auto it = mp[x].find(j);
			if(it != mp[x].end()) r += it->second;
		}
		return r;
	}
	int squr(int x,int y,int xx,int yy){
		if(xx<x||yy<y) return 0;
		return qur(xx,yy) - qur(x-1,yy) - qur(xx,y-1) + qur(x-1,y-1); 
	}
}b11,b12,b21,b22;
set<pair<int,int> > s;
int xmn,xmx,ymn,ymx;

void init(int R,int C,int sr,int sc,int M,char* S){
	b11.init(R,C);
	b21.init(R,C);
	b12.init(R,C);
	b22.init(R,C);
	s.clear();
	s.insert({sr,sc}); xmn = xmx = sr, ymn = ymx = sc;
	for(int j=0;j<M;j++){
		char &i = S[j];
		if(i == 'N') sr--;
		else if(i == 'E') sc++;
		else if(i == 'W') sc--;
		else if(i == 'S') sr++;
		s.insert({sr,sc});
		xmx = max(xmx,sr);
		xmn = min(xmn,sr);
		ymx = max(ymx,sc);
		ymn = min(ymn,sc);
	}
	vector<pair<int,int> > v(s.begin(),s.end());
	for(auto i : v){
		b11.add(i.first,i.second,1);
		int cnt = 0;
		if(s.find({i.first+1,i.second}) != s.end()) 
			b21.add(i.first,i.second,1),cnt++; //vert
		if(s.find({i.first,i.second+1}) != s.end())	
			b12.add(i.first,i.second,1),cnt++; //hori
		if(s.find({i.first+1,i.second+1}) != s.end()) cnt++;
		if(cnt == 3) b22.add(i.first,i.second,1);
	}
}

int colour(int ar,int ac,int br,int bc){
	int v11 = (br-ar+bc-ac+4)*2 + b11.squr(ar,ac,br,bc);
	int v21 = (br-ar+2)*2 + b21.squr(ar,ac,br-1,bc) + b11.squr(br,ac,br,bc) + b11.squr(ar,ac,ar,bc);
	int v12 = (bc-ac+2)*2 + b12.squr(ar,ac,br,bc-1) + b11.squr(ar,bc,br,bc) + b11.squr(ar,ac,br,ac);
	int v22 = b22.squr(ar,ac,br-1,bc-1) + 
				b12.squr(ar,ac,ar,bc-1) + b12.squr(br,ac,br,bc-1) + 
				b21.squr(ar,ac,br-1,ac) + b21.squr(ar,bc,br-1,bc);
	if(s.find({ar,ac}) != s.end()) v22++;
	if(s.find({br,ac}) != s.end()) v22++;
	if(s.find({ar,bc}) != s.end()) v22++;
	if(s.find({br,bc}) != s.end()) v22++;
	//cout << b11.squr(ar,ac,br,bc) << '\n';
	//cout << v11 << ' ' << v12 << ' ' << v21 << ' ' << v22 << '\n';
	return v21 + v12 - v11 - v22 + 1 + (ar < xmn && ac < ymn && br > xmx && bc > ymx);
}

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