Submission #466356

#TimeUsernameProblemLanguageResultExecution timeMemory
466356ivan_tudorRoads (CEOI20_roads)C++14
0 / 100
62 ms3608 KiB
#include<bits/stdc++.h> using namespace std; const int N = 1e5+ 5; struct points{ int x, y; int type; int id; bool operator <(points oth) const{ if(y == oth.y) return id < oth.id; return y < oth.y; } }; set<points> act; pair<int, int> upper[N], lower[N]; bool cmp(points a, points b){ if(a.x == b.x) return a.type < b.type; return a.x < b.x; } int v[N][4]; pair<int, int> general = {INT_MIN, INT_MIN}; int main() { //freopen(".in","r",stdin); ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n; cin>>n; vector<points> ev; for(int i =1 ; i <=n; i++){ int x1, y1, x2, y2; cin>>x1>>y1>>x2>>y2; if(x1 >x2){ swap(x1, x2); swap(y1, y2); } v[i][0] = x1; v[i][1] = y1; v[i][2] = x2; v[i][3] = y2; if(x1 == x2){ ev.push_back({x1, y1, 2, i}); ev.push_back({x1, y1, -1, i}); } else{ ev.push_back({x1, y1, 1, i}); ev.push_back({x2, y2, 0, i}); } } sort(ev.begin(), ev.end(), cmp); for(auto e : ev){ if(e.type == 1){ pair<int, int> last = {INT_MIN, INT_MIN}; auto nxt = act.upper_bound({e}); if(nxt != act.end()){ last = upper[(*nxt).id]; upper[(*nxt).id] = {e.x, e.y}; } if(nxt != act.begin()){ nxt = prev(nxt); if(lower[(*nxt).id].first > last.first) last = lower[(*nxt).id]; lower[(*nxt).id] = {e.x, e.y}; } if(last.first == INT_MIN) last = general; if(last.first != INT_MIN){ cout<<last.first<<" "<<last.second<<" "<<e.x<<" "<<e.y<<"\n"; } act.insert({e.x, e.y, 0, e.id}); upper[e.id] = {e.x, e.y}; lower[e.id] = {e.x, e.y}; } else if(e.type == 0){ auto itr = act.find({v[e.id][0], v[e.id][1], 0, e.id}); assert(itr != act.end()); auto nxt = next(itr); if(nxt != act.end()){ upper[(*nxt).id] = {e.x, e.y}; } if(itr != act.begin()){ nxt = prev(itr); lower[(*nxt).id] = {e.x, e.y}; } act.erase({v[e.id][0], v[e.id][1], 0, e.id}); } else if(e.type == -1){ int ys = v[e.id][1], yf = v[e.id][3]; if(ys > yf) swap(ys, yf); pair<int, int> last = {INT_MIN, INT_MIN}; int tp = 0; auto nxt = act.upper_bound({0, yf, 0, e.id}); if(nxt != act.end()){ last = upper[(*nxt).id]; tp = 1; upper[(*nxt).id] = {e.x, yf}; } if(nxt != act.begin()){ nxt = prev(nxt); if(lower[(*nxt).id].first > last.first) last = lower[(*nxt).id], tp = 2; lower[(*nxt).id] = {e.x, ys}; } if(tp == 1){ cout<<last.first<<" "<<last.second<<" "<<e.x<<" "<<yf<<"\n"; } else if(tp == 2){ cout<<last.first<<" "<<last.second<<" "<<e.x<<" "<<ys<<"\n"; } else if(general.first != INT_MIN) cout<<general.first<<" "<<general.second<<" "<<e.x<<" "<<ys<<"\n"; act.insert({e.x, v[e.id][1], 0, e.id}); } else if(e.type == 2){ act.erase({e.x, v[e.id][1], 0, e.id}); } general = {e.x, e.y}; } return 0; }
#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...