Submission #1298647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298647		PieArmy	Roads (CEOI20_roads)	C++20	0 / 100	1 ms	14400 KiB

roads

#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){
		sort(v.begin(),v.end());
		pair<int,int>las;
		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;
				}
				else{
					cout<<p.fr<<" "<<y<<" "<<las.fr<<" "<<y<<endl;
				}
			}
			las=p;
		}
		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;
		}
	}
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 40