oj.uz

Submission #105409

# Submission time Handle Problem Language Result Execution time Memory
105409 2019-04-12T01:59:14 Z puyu_liao Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 2056 ms 180088 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 45 ms 44152 KB Output is correct
2 Correct 44 ms 44280 KB Output is correct
3 Correct 1149 ms 55772 KB Output is correct
4 Correct 1758 ms 62380 KB Output is correct
5 Correct 1763 ms 63880 KB Output is correct
6 Correct 1657 ms 62732 KB Output is correct
7 Correct 1481 ms 58604 KB Output is correct
8 Correct 836 ms 45056 KB Output is correct
9 Correct 1775 ms 63124 KB Output is correct
10 Correct 2056 ms 63960 KB Output is correct
11 Correct 1933 ms 62820 KB Output is correct
12 Correct 399 ms 60144 KB Output is correct
13 Correct 413 ms 62392 KB Output is correct
14 Correct 460 ms 63856 KB Output is correct
15 Correct 526 ms 62968 KB Output is correct
16 Correct 1421 ms 58260 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 787 ms 113548 KB Output is correct
3 Correct 593 ms 128000 KB Output is correct
4 Correct 1331 ms 180088 KB Output is correct
5 Correct 633 ms 111736 KB Output is correct
6 Correct 264 ms 51832 KB Output is correct
7 Incorrect 429 ms 57632 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 -