oj.uz

Submission #105408

# Submission time Handle Problem Language Result Execution time Memory
105408 2019-04-12T01:50:02 Z puyu_liao Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1802 ms 180060 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 44280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 44152 KB Output is correct
2 Correct 44 ms 44160 KB Output is correct
3 Correct 1014 ms 55936 KB Output is correct
4 Correct 1802 ms 62536 KB Output is correct
5 Correct 1707 ms 63968 KB Output is correct
6 Correct 1648 ms 62880 KB Output is correct
7 Correct 1454 ms 58556 KB Output is correct
8 Correct 708 ms 45180 KB Output is correct
9 Correct 1569 ms 62888 KB Output is correct
10 Correct 1675 ms 64064 KB Output is correct
11 Correct 1656 ms 62920 KB Output is correct
12 Correct 374 ms 60232 KB Output is correct
13 Correct 426 ms 62356 KB Output is correct
14 Correct 436 ms 63904 KB Output is correct
15 Correct 554 ms 62708 KB Output is correct
16 Correct 1128 ms 58412 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 44152 KB Output is correct
2 Correct 781 ms 113708 KB Output is correct
3 Correct 568 ms 128208 KB Output is correct
4 Correct 1249 ms 180060 KB Output is correct
5 Correct 640 ms 111644 KB Output is correct
6 Correct 222 ms 51636 KB Output is correct
7 Incorrect 412 ms 57720 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 44280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 44280 KB Output isn't correct
2 Halted 0 ms 0 KB -