oj.uz

답안 #114308

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
114308 2019-05-31T19:13:38 Z dorijanlendvaj 무지개나라 (APIO17_rainbow) C++14
12 / 100
 148 ms 16376 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back

using namespace std;
using namespace __gnu_pbds;
using ll=long long;

int dx[]={0,1,0,-1,1,1,-1,-1};
int dy[]={1,0,-1,0,1,-1,1,-1};
int n,m;
set<pii> s;
vector<pii> ou,prr;
const int SZ=32987,N=200010;
int c1[N],c2[N],c3[N];
vector<pair<ll,int>> ht[SZ],ht1[SZ];
vector<int> sv,sv1;

void change(ll i,int x,bool t)
{
	if (t==0)
	{
		ll i1=i;
		i+=1872432922ll;
		i^=0x95872901;
		i%=SZ;
		//cout<<i<<' '<<i1<<endl;
		for (auto &a: ht[i]) if (a.x==i1)
		{
			a.y=x;
		//	cout<<"found"<<endl;
			return;
		}
		//cout<<"made"<<endl;
		ht[i].pb({i1,x});
		sv.pb(i);
	}
	else
	{
		ll i1=i;
		i+=1872432922ll;
		i^=0x95872901;
		i%=SZ;
		for (auto &a: ht1[i]) if (a.x==i1)
		{
			a.y=x;
			return;
		}
		ht1[i].pb({i1,x});
		sv1.pb(i);
	}
}

int get(ll i,bool t)
{
	if (t==0)
	{
		ll i1=i;
		i+=1872432922ll;
		i^=0x95872901;
		i%=SZ;
		//cout<<i<<endl;
		for (auto a: ht[i]) if (a.x==i1) return a.y;
		return 0;
	}
	else
	{
		ll i1=i;
		i+=1872432922ll;
		i^=0x95872901;
		i%=SZ;
		for (auto a: ht1[i]) if (a.x==i1) return a.y;
		return 0;
	}
}

void clearHT(bool t)
{
	if (t==0)
	{
		for (auto a: sv) ht[a].clear();
		sv.clear();
	}
	else
	{
		for (auto a: sv1) ht1[a].clear();
		sv1.clear();
	}
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	set<pii> pros;
	n=R;
	m=C;
	--sr;
	--sc;
	for (int i=0;i<M;++i)
	{
		//if (s.find({sr,sc})!=s.end()) s.erase({sr,sc});
		pros.insert({sr,sc});
		if (S[i]=='W') --sc;
		if (S[i]=='E') ++sc;
		if (S[i]=='N') --sr;
		if (S[i]=='S') ++sr;
	}
	pros.insert({sr,sc});
	for (auto a: pros) prr.pb(a);
	for (auto a: prr) change(a.x*200000ll+a.y,1,1);
	//for (auto a: ou) cout<<a.x<<' '<<a.y<<endl;
	for (int i=0;i<m;++i)
	{
		c1[i+1]=c1[i];
		if (get(i,1)!=1 && (i==0 || get(i-1,1)==1)) ++c1[i+1];
		c2[i+1]=c2[i];
		if (get(i+200000,1)!=1 && (i==0 || get(i+199999,1)==1)) ++c2[i+1];
		c3[i+1]=c3[i];
		int a=(get(i+200000,1)==1)*2+(get(i,1)==1);
		int b;
		if (i==0) b=3;
		else b=(get(i+199999,1)==1)*2+(get(i-1,1)==1);
		if (b==3 && a!=3) ++c3[i+1];
	}
}

int cnt,z[61][61],par[1000050];
bool bio[100050];
vector<int> sss;
bool pos[1000050];
vector<int> nap;
//gp_hash_table<ll,int> nodes;

void add(int i)
{
	nap.pb(i);
	par[i]=i;
	pos[i]=1;
	++cnt;
}

int find(int i)
{
	if (!pos[i]) return -1;
	if (i==par[i]) return i;
	return par[i]=find(par[i]);
}

void merge(int a,int b)
{
	a=find(a);
	b=find(b);
	if (a==-1 || b==-1) return;
	if (a==b) return;
	par[a]=b;
	--cnt;
}

void clear()
{
	for (auto x: nap)
	{
		par[x]=-1;
		pos[x]=0;
	}
	nap.clear();
	cnt=0;
}
int colour(int ar, int ac, int br, int bc) {
	int x1=ar-1,x2=br,y1=ac-1,y2=bc;
	int ans=(y1 && ((x1==0 && get(y1-1,1)!=1 && get(y1,1)!=1) || (x2==2 && get(y1+200000-1,1)!=1 && get(y1+200000,1)!=1)));
	if (x1==0)
	{
		if (x2==1) return c1[y2]-c1[y1]+ans;
		else return c3[y2]-c3[y1]+ans;
	}
	else return c2[y2]-c2[y1]+ans;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1920 KB Output is correct
2 Correct 3 ms 1920 KB Output is correct
3 Correct 102 ms 12756 KB Output is correct
4 Correct 133 ms 16236 KB Output is correct
5 Correct 148 ms 16376 KB Output is correct
6 Correct 127 ms 15060 KB Output is correct
7 Correct 118 ms 14824 KB Output is correct
8 Correct 81 ms 7928 KB Output is correct
9 Correct 134 ms 16232 KB Output is correct
10 Correct 133 ms 16364 KB Output is correct
11 Correct 128 ms 15060 KB Output is correct
12 Correct 94 ms 15596 KB Output is correct
13 Correct 112 ms 16308 KB Output is correct
14 Correct 105 ms 16296 KB Output is correct
15 Correct 98 ms 15084 KB Output is correct
16 Correct 113 ms 13992 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1920 KB Output is correct
2 Incorrect 57 ms 12780 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -