Submission #624450

#TimeUsernameProblemLanguageResultExecution timeMemory
624450Vladth11Roads (CEOI20_roads)C++14
0 / 100
102 ms11692 KiB
#include <bits/stdc++.h> #define debug(x) cerr << #x << " " << x << "\n" #define debugs(x) cerr << #x << " " << x << " " using namespace std; typedef long long ll; typedef pair <long double, long double> pii; const ll NMAX = 100001; const ll VMAX = 101; const ll INF = 1e9; const ll MOD = 1000000007; const ll BLOCK = 447; const ll base = 117; const ll nr_of_bits = 18; const ll inv2 = 500000004; struct event { pii x; int stare; bool operator < (const event a) { if(a.x.first != x.first) { return x.first < a.x.first; } if(a.stare != stare) { return stare > a.stare; } return x.second > a.x.second; /// Nu ar trb sa aiba importanta, dar e necesar sa nu busesc sortarea } }; struct segment { int a, b, c, d; int idx; } sgt[NMAX]; vector <event> events; map <pii, pii> mp; int n; bool signs(int a, int b){ if(a < b) swap(a, b); if(a > 0 && b < 0) return 0; return 1; } void adauga(int a, int b){ if(a > n - 2) assert(0 == 1); if(b > n - 2) assert(0 == 1); segment first = sgt[a]; segment second = sgt[b]; if(first.b < second.b){ swap(first, second); }else if(first.b == second.b){ if(first.a < second.a){ swap(first, second); } } if(first.a >= second.c){ cout << first.a << " " << first.b << " " << second.c << " " << second.d << "\n"; return; } cout << first.a << " " << first.b << " " << second.a << " " << second.b << "\n"; } int main() { //ifstream cin(".in"); //ofstream cout(".out"); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int i; cin >> n; for(i = 1; i <= n; i++) { int a, b, c, d; cin >> a >> b >> c >> d; if(a > c) { swap(b, d); swap(a, c); } else if(a == c) { if(b > d) swap(b, d); /// nu stiu daca e nevoie } sgt[i] = {a, b, c, d, i}; events.push_back({{a, b}, i}); events.push_back({{c, d}, -i}); } n += 2; sgt[n - 1] = {-INF, -INF, INF, -INF, n - 1}; events.push_back({{-INF, -INF}, n - 1}); events.push_back({{INF, -INF}, -(n - 1)}); sgt[n] = {-INF, INF, INF, INF, n}; events.push_back({{-INF, INF}, n}); events.push_back({{INF, INF}, -n}); sort(events.begin(), events.end()); set <pii> active; vector <pair <pii, int> > facut; for(int i = 0; i < events.size(); i++) { if(events[i].stare > 0){ active.insert({events[i].x.second, events[i].stare}); if(events[i].x.first != -INF) facut.push_back({events[i].x, events[i].stare}); }else{ active.erase({events[i].x.second, -events[i].stare}); } if(i == events.size() || (events[i + 1].x.first != events[i].x.first || !signs(events[i + 1].stare, events[i].stare))){ for(auto x : facut){ auto sus = active.upper_bound({x.first.second, -1}); sus = prev(sus); auto jos = active.lower_bound({x.first.second + 1, -1}); int indS = (*sus).second; int indJ = (*jos).second; if(mp.find({indS, indJ}) == mp.end()){ if(sgt[indS].a != -INF){ adauga(indS, x.second); }else if(sgt[indJ].a != -INF){ adauga(indJ, x.second); } }else{ pii conectare = mp[{indS, indJ}]; adauga(conectare.second, x.second); } mp[{indS, indJ}] = max(mp[{indS, indJ}], {x.first.first, x.second}); } facut.clear(); } } return 0; }

Compilation message (stderr)

roads.cpp: In function 'int main()':
roads.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i = 0; i < events.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
roads.cpp:111:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         if(i == events.size() || (events[i + 1].x.first != events[i].x.first || !signs(events[i + 1].stare, events[i].stare))){
      |            ~~^~~~~~~~~~~~~~~~
#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...