Submission #1298644

#TimeUsernameProblemLanguageResultExecution timeMemory
1298644PieArmyRoads (CEOI20_roads)C++20
15 / 100
38 ms23312 KiB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

int n;
pair<pair<int,int>,pair<int,int>>arr[100023];
map<int,vector<pair<int,int>>>mp;
map<int,int>st;

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i].fr.fr>>arr[i].fr.sc>>arr[i].sc.fr>>arr[i].sc.sc;
		if(arr[i].fr>arr[i].sc)swap(arr[i].fr,arr[i].sc);
		mp[arr[i].fr.sc].pb({arr[i].fr.fr,1});
		if(arr[i].fr.sc==arr[i].sc.sc){
			mp[arr[i].sc.sc].pb({arr[i].sc.fr,0});
		}
		else mp[arr[i].sc.sc].pb({arr[i].sc.fr,-1});
	}
	for(auto&[y,v]:mp){
		for(auto p:v){
			if(p.sc==1){
				if(st.size()){
					auto itr=st.lower_bound(p.fr);
					if(itr==st.end()){
						itr--;
					}
					cout<<p.fr<<" "<<y<<" "<<itr->fr<<" "<<itr->sc<<endl;
				}
			}
		}
		pair<int,int>las;
		for(auto p:v){
			st[p.fr]=y;
			if(p.sc==0){
				while(true){
					auto itr=--st.lower_bound(p.fr);
					if(itr->fr==las.fr)break;
					st.erase(itr);
				}
			}
			las=p;
		}
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...