| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 624449 | Vladth11 | Roads (CEOI20_roads) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
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 n, 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;
}