oj.uz

Submission #105410

# Submission time Handle Problem Language Result Execution time Memory
105410 2019-04-12T02:26:37 Z puyu_liao Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1826 ms 179996 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 - v11 - v22 + v12 + 1 + (ar < xmn && ac < ymn && br > xmx && bc > ymx);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 44160 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 55 ms 44164 KB Output is correct
2 Correct 45 ms 44152 KB Output is correct
3 Correct 1189 ms 55836 KB Output is correct
4 Correct 1577 ms 62408 KB Output is correct
5 Correct 1826 ms 63980 KB Output is correct
6 Correct 1705 ms 62704 KB Output is correct
7 Correct 1591 ms 58660 KB Output is correct
8 Correct 771 ms 45136 KB Output is correct
9 Correct 1509 ms 63000 KB Output is correct
10 Correct 1595 ms 63980 KB Output is correct
11 Correct 1541 ms 62564 KB Output is correct
12 Correct 451 ms 60032 KB Output is correct
13 Correct 431 ms 62412 KB Output is correct
14 Correct 437 ms 63832 KB Output is correct
15 Correct 451 ms 62584 KB Output is correct
16 Correct 1119 ms 58376 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 823 ms 113464 KB Output is correct
3 Correct 618 ms 128124 KB Output is correct
4 Correct 1396 ms 179996 KB Output is correct
5 Correct 659 ms 111608 KB Output is correct
6 Correct 303 ms 51820 KB Output is correct
7 Incorrect 450 ms 57776 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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