Submission #466351

#TimeUsernameProblemLanguageResultExecution timeMemory
466351ivan_tudorRoads (CEOI20_roads)C++14
0 / 100
2 ms332 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]; 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}); } 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 == 0){ 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){ 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 == 1){ 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{ 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"; } } } return 0; }

Compilation message (stderr)

roads.cpp: In function 'int main()':
roads.cpp:24:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   freopen(".in","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~
#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...