Submission #1315777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315777		JuanJL	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	0 ms	332 KiB

dango_maker

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef int ll;

string o = "RGW";
short cnt;
set<pair<pair<short,short>,short>>::iterator jj;

set<pair<short,pair<short,pair<short,short>>>> opc;


pair<pair<short,short>,short> aux;
set<pair<pair<short,short>,short>> ver;
set<pair<pair<short,short>,short>> hor;


//sign 
// 1 = vertical
// -1 = horizontal
ll col(pair<pair<short,short>,short> x,set<pair<pair<short,short>,short>> &voh, short sign){ 

//	cout<<x.fst.fst<<" "<<x.fst.snd<<" "<<sign<<'\n';
	cnt = 0;
	pair<short,short> i = x.fst;
	aux.snd=0;

	aux.fst=i;
	jj=voh.lower_bound(aux);
	if(jj!=voh.end() && (*jj).fst==aux.fst){
		cnt++;
	}
				
	aux.fst={i.fst+(1*sign),i.snd-(1*sign)};
	jj=voh.lower_bound(aux);
	if(jj!=voh.end() && (*jj).fst==aux.fst){
		cnt++;
	}
	
	aux.fst={i.fst+(2*sign),i.snd-(2*sign)};
	jj=voh.lower_bound(aux);
	if(jj!=voh.end() && (*jj).fst==aux.fst){
		cnt++;
	}

//	cout<<"new cnt "<<cnt<<'\n';

	opc.erase(opc.find({x.snd,{sign,i}}));
	opc.insert({cnt,{sign,i}});

	if(sign==1){
		ver.erase(ver.find(x));
		ver.insert({i,cnt});
	}else{
		hor.erase(hor.find(x));
		hor.insert({i,cnt});
	}

//	cout<<"return\n";
	return cnt;		
}

void recol(pair<pair<short,short>,short> x, set<pair<pair<short,short>,short>> &voh , short sign){
	pair<short,short> i = x.fst;
	aux.snd=0;

	aux.fst=i;
	jj=voh.lower_bound(aux);
	if(jj!=voh.end() && (*jj).fst==aux.fst){
		if(sign==1) col(*jj,hor,-1);
		else col(*jj,ver,1);
	}
				
	aux.fst={i.fst+(1*sign),i.snd-(1*sign)};
	jj=voh.lower_bound(aux);
	if(jj!=voh.end() && (*jj).fst==aux.fst){
		if(sign==1) col(*jj,hor,-1);
		else col(*jj,ver,1);
	}
	
	aux.fst={i.fst+(2*sign),i.snd-(2*sign)};
	jj=voh.lower_bound(aux);
	if(jj!=voh.end() && (*jj).fst==aux.fst){
		if(sign==1) col(*jj,hor,-1);
		else col(*jj,ver,1);
	}
}

void rem(pair<pair<short,short>,short> x, set<pair<pair<short,short>,short>> &voh , short sign){
	pair<short,short> i = x.fst;
	aux.snd=0;

	aux.fst=i;
	jj=voh.lower_bound(aux);
	if(jj!=voh.end() && (*jj).fst==aux.fst){
		voh.erase(jj);
		opc.erase(opc.find({(*jj).snd,{sign*-1,(*jj).fst}}));
		if(sign==1) recol(*jj,ver,-1);
		else recol(*jj,hor,1);
	}
			
	aux.fst={i.fst+(1*sign),i.snd-(1*sign)};
	jj=voh.lower_bound(aux);
	if(jj!=voh.end() && (*jj).fst==aux.fst){
		voh.erase(jj);
		opc.erase(opc.find({(*jj).snd,{sign*-1,(*jj).fst}}));
		if(sign==1) recol(*jj,ver,-1);
		else recol(*jj,hor,1);
	}
	
	aux.fst={i.fst+(2*sign),i.snd-(2*sign)};
	jj=voh.lower_bound(aux);
	if(jj!=voh.end() && (*jj).fst==aux.fst){
		voh.erase(jj);
		opc.erase(opc.find({(*jj).snd,{sign*-1,(*jj).fst}}));
		if(sign==1) recol(*jj,ver,-1);
		else recol(*jj,hor,1);
	}
}



int main(){ FIN;
	ll n,m; cin>>n>>m;
	vector<string> s(n); forn(i,0,n) cin>>s[i];

	
	bool vert;
	bool hori;
	forn(i,0,n){
		forn(j,0,m){
			vert = true;
			hori = true;
			forn(h,0,3){
				if(i+h>=n || s[i+h][j]!=o[h]) vert=false;
				if(j+h>=m || s[i][j+h]!=o[h]) hori=false;
			}
	
			if(vert) ver.insert({{i,j},0}), opc.insert({0,{1,{i,j}}});//, cout<<"vert "<<i<<" "<<j<<'\n';
			if(hori) hor.insert({{i,j},0}), opc.insert({0,{-1,{i,j}}});//, cout<<"hori "<<i<<" "<<j<<'\n';
		}
	}
//	cout<<"llegamos\n";
	for(auto i:ver) col(i,hor,1);
	for(auto i:hor) col(i,ver,-1);
//	cout<<"colisiones listas\n";
	
	ll res = 0;
	while(true){
		if(SZ(opc)==0) break;

		res++;
		pair<short,pair<short,pair<short,short>>> best = *opc.begin();
		opc.erase(opc.begin());
		
		if(best.snd.fst==1){
			ver.erase(ver.find({best.snd.snd,best.fst}));
			rem({best.snd.snd,best.fst},hor,1);
		}else{
			hor.erase(hor.find({best.snd.snd,best.fst}));
			rem({best.snd.snd,best.fst},ver,-1);
		}
	}

	cout<<res<<'\n';
	
	return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67