oj.uz

Submission #105407

# Submission time Handle Problem Language Result Execution time Memory
105407 2019-04-12T01:40:45 Z puyu_liao Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 2040 ms 180216 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;

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});
	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});
	}
	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;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 44284 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 42 ms 44152 KB Output is correct
2 Correct 120 ms 44200 KB Output is correct
3 Correct 1102 ms 58740 KB Output is correct
4 Correct 1657 ms 65348 KB Output is correct
5 Correct 1524 ms 66672 KB Output is correct
6 Correct 1549 ms 65644 KB Output is correct
7 Correct 1367 ms 61544 KB Output is correct
8 Correct 744 ms 47864 KB Output is correct
9 Correct 1596 ms 65844 KB Output is correct
10 Correct 1825 ms 66728 KB Output is correct
11 Correct 2040 ms 65632 KB Output is correct
12 Correct 364 ms 62960 KB Output is correct
13 Correct 456 ms 65076 KB Output is correct
14 Correct 451 ms 66636 KB Output is correct
15 Correct 494 ms 65508 KB Output is correct
16 Correct 1295 ms 61276 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 44160 KB Output is correct
2 Correct 820 ms 113708 KB Output is correct
3 Correct 600 ms 128216 KB Output is correct
4 Correct 1311 ms 180216 KB Output is correct
5 Correct 599 ms 111708 KB Output is correct
6 Correct 270 ms 51832 KB Output is correct
7 Incorrect 424 ms 57948 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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