Submission #1315693

#TimeUsernameProblemLanguageResultExecution timeMemory
1315693JuanJLDango Maker (JOI18_dango_maker)C++20
0 / 100
0 ms332 KiB
#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 long long ll;

string o = "RGW";

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

	vector<pair<ll,ll>> ver;
	vector<pair<ll,ll>> hor;
	forn(i,0,n){
		forn(j,0,m){
			bool vert = true;
			bool 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.pb({i,j}) ;//, cout<<"vert "<<i<<" "<<j<<'\n';
			if(hori) hor.pb({i,j}) ;//, cout<<"hori "<<i<<" "<<j<<'\n';
		}
	}

	set<pair<ll,ll>> colv[n+5][m+5];
	set<pair<ll,ll>> colh[n+5][m+5];
	
	//cout<<"precalculos listos\n";

	set<pair<ll,pair<ll,ll>>> opc;

	forn(i,0,SZ(ver)){
		ll cnt = 0;
		ll j1=lower_bound(ALL(hor),ver[i])-hor.begin();
		if(j1!=SZ(hor) && hor[j1]==ver[i]){
			cnt++;
			colv[ver[i].fst][ver[i].snd].insert({ver[i]});
		}
		
		ll j2=lower_bound(ALL(hor),pair<ll,ll>{ver[i].fst+1,ver[i].snd-1}) - hor.begin();
		if(j2!=SZ(hor) && hor[j2]==pair<ll,ll>{ver[i].fst+1,ver[i].snd-1}){
			cnt++;
			colv[ver[i].fst][ver[i].snd].insert(pair<ll,ll>{ver[i].fst+1,ver[i].snd-1});
		}


		ll j3=lower_bound(ALL(hor),pair<ll,ll>{ver[i].fst+2,ver[i].snd-2}) - hor.begin();
		if(j3!=SZ(hor) && hor[j3]==pair<ll,ll>{ver[i].fst+2,ver[i].snd-2}){
			cnt++;
			colv[ver[i].fst][ver[i].snd].insert(pair<ll,ll>{ver[i].fst+2,ver[i].snd-2});
		}

		opc.insert({cnt,{0,i}});
	}

	//cout<<"intersecciones verticales listas\n";

	forn(i,0,SZ(hor)){
		ll cnt = 0;
		ll j1=lower_bound(ALL(ver),hor[i])-ver.begin();
		if(j1!=SZ(ver) && ver[j1]==hor[i]){
			cnt++;
			colh[hor[i].fst][hor[i].snd].insert(hor[i]);
		}
			
		ll j2=lower_bound(ALL(ver),pair<ll,ll>{hor[i].fst-1,hor[i].snd+1}) - ver.begin();
		if(j2!=SZ(ver) && ver[j2]==pair<ll,ll>{hor[i].fst-1,hor[i].snd+1}){
			cnt++;
			colh[hor[i].fst][hor[i].snd].insert(pair<ll,ll>{hor[i].fst-1,hor[i].snd+1});
		}

		ll j3=lower_bound(ALL(ver),pair<ll,ll>{hor[i].fst-2,hor[i].snd+2}) - ver.begin();
		if(j3!=SZ(ver) && ver[j3]==pair<ll,ll>{hor[i].fst-2,hor[i].snd+2}){
			cnt++;
			colh[hor[i].fst][hor[i].snd].insert(pair<ll,ll>{hor[i].fst-2,hor[i].snd+2});
		}
		
		opc.insert({cnt,{1,i}});
	}

	//cout<<"intersecciones horizontales listas\n";


	ll res = 0;
	while(true){

		if(SZ(opc)==0) break;
		
		res++;

		pair<ll,pair<ll,ll>> best = *opc.begin();
		opc.erase(opc.begin());
		//cout<<best.fst<<" "<<best.snd.fst<<" "<<best.snd.snd<<'\n';
		if(best.snd.fst==0){
			ll i=ver[best.snd.snd].fst;
			ll j=ver[best.snd.snd].snd;
			
			for(auto [ni,nj] : colv[i][j]){
				ll ind = lower_bound(ALL(hor),pair<ll,ll>{ni,nj})-hor.begin();
				colh[ni][nj].erase(colh[ni][nj].find({i,j}));
				opc.erase(opc.find({SZ(colh[ni][nj]),{1,ind}}));
				
				for(auto [nni,nnj] : colh[ni][nj]){
					if(nni==i && nnj==j) continue;
					ll nind = lower_bound(ALL(ver),pair<ll,ll>{nni,nnj})-ver.begin();
					opc.erase(opc.find({SZ(colv[nni][nnj]),{0,nind}}));
					colv[nni][nnj].erase(colv[nni][nnj].find({ni,nj}));
					opc.insert({SZ(colv[nni][nnj]),{0,nind}});
				}
				
				while(!colh[ni][nj].empty()) colh[ni][nj].erase(colh[ni][nj].begin());
			}
			while(!colv[i][j].empty()) colv[i][j].erase(colv[i][j].begin());
			
		}else{
			ll i=hor[best.snd.snd].fst;
			ll j=hor[best.snd.snd].snd;
				
			for(auto [ni,nj] : colh[i][j]){
				ll ind = lower_bound(ALL(ver),pair<ll,ll>{ni,nj})-ver.begin();
				opc.erase(opc.find({SZ(colv[ni][nj]),{0,ind}}));
				
				for(auto [nni,nnj] : colv[ni][nj]){
					if(nni==i && nnj == j) continue;
					ll nind = lower_bound(ALL(hor),pair<ll,ll>{nni,nnj})-hor.begin();
					opc.erase(opc.find({SZ(colh[nni][nnj]),{1,nind}}));
					colh[nni][nnj].erase(colh[nni][nnj].find({ni,nj}));
					opc.insert({SZ(colh[nni][nnj]),{1,nind}});
				}
				while(!colv[ni][nj].empty()) colv[ni][nj].erase(colv[ni][nj].begin());

			}
			while(!colh[i][j].empty()) colh[i][j].erase(colh[i][j].begin());
		}
		
		
	}

	cout<<res<<'\n';
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...