| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 624526 |
2022-08-08T12:18:14 Z |
Vladth11 |
Roads (CEOI20_roads) |
C++14 |
|
164 ms |
10684 KB |
#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 <int, int> 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;
set <pii> exista;
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
}
};
int swipex;
struct segment {
int a, b, c, d;
int idx;
long double gety() {
if(c != a)
return (long double)b + (long double)(swipex - a) * (long double)(d - b) / (long double)(c - a);
else
return (long double)b;
}
} sgt[NMAX];
vector <event> events;
map <pii, pii> mp;
set <pii> already;
bool signs(int a, int b) {
if(a < b)
swap(a, b);
if(a > 0 && b < 0)
return 0;
return 1;
}
int cnt = 0;
void adauga(int a, int b) {
if(a < b)
swap(a, b);
cnt++;
if(already.find({a, b}) != already.end()) return;
already.insert({a, b});
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;
}
if(second.a >= first.c) {
cout << first.c << " " << first.d << " " << second.a << " " << second.b << "\n";
return;
}
cout << first.a << " " << first.b << " " << second.a << " " << second.b << "\n";
}
struct ura {
int first, second;
bool operator < (const ura a)const {
if(a.second == -1 && second == -1) {
return first < a.first;
}
if(a.second == -1) {
return sgt[second].gety() < a.first;
}
if(second == -1) {
return first < sgt[a.second].gety();
}
return sgt[second].gety() < sgt[a.second].gety();
}
};
int main() {
//ifstream cin(".out");
//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};
exista.insert({a, b});
exista.insert({c, d});
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 <ura> active;
vector <pair <pii, int> > facut;
vector <pii> tobe;
for(int i = 0; i < events.size(); i++) {
swipex = events[i].x.first;
if(events[i].stare > 0) {
if(events[i].x.first != -INF) {
facut.push_back({events[i].x, events[i].stare});
tobe.push_back({events[i].x.second, events[i].stare});
} else {
active.insert({events[i].x.second, events[i].stare});
}
} else {
if(-events[i].stare < n - 1) {
auto sus = active.lower_bound({sgt[-events[i].stare].gety(), -1});
sus = prev(sus);
auto jos = active.lower_bound({sgt[-events[i].stare].gety(), -1});
jos = next(jos);
int indS = (*sus).second;
int indJ = (*jos).second;
if(mp.find({indS, indJ}) != mp.end())
mp[ {indS, indJ}] = max(mp[ {indS, indJ}], {events[i].x.first, -events[i].stare});
else
mp[ {indS, indJ}] = {events[i].x.first, -events[i].stare};
}
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))) {
int cc = 0;
if(facut.size() == 0) continue;
for(auto x : facut) {
cc++;
/// pe primul vrem sa-l conectam la alea din spate
if(cc == 1) {
active.insert({tobe[0].first, tobe[0].second});
}
auto sus = active.lower_bound({x.first.second, -1});
sus = prev(sus);
auto jos = active.lower_bound({x.first.second, -1}); /// nu vrem daca trece chiar la limita sa-l ignor
jos = next(jos);
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);
}
if(cc == 1) {
for(auto x : tobe) {
active.insert({x.first, x.second});
}
}
/// Desi il conectam in urma, vrem ca atunci cand e inserat sa tina cont si de ceilalti
sus = active.lower_bound({x.first.second, -1});
sus = prev(sus);
jos = active.lower_bound({x.first.second, -1}); /// nu vrem daca trece chiar la limita sa-l ignor
jos = next(jos);
indS = (*sus).second;
indJ = (*jos).second;
if(mp.find({indS, indJ}) != mp.end())
mp[ {indS, indJ}] = max(mp[ {indS, indJ}], {x.first.first, x.second});
else
mp[ {indS, indJ}] = {x.first.first, x.second};
}
tobe.clear();
facut.clear();
}
}
assert(cnt == n - 3);
return 0;
}
Compilation message
roads.cpp: In function 'int main()':
roads.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int i = 0; i < events.size(); i++) {
| ~~^~~~~~~~~~~~~~~
roads.cpp:149:74: warning: narrowing conversion of 'sgt[(- events.std::vector<event>::operator[](((std::vector<event>::size_type)i)).event::stare)].segment::gety()' from 'long double' to 'int' [-Wnarrowing]
149 | auto sus = active.lower_bound({sgt[-events[i].stare].gety(), -1});
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~
roads.cpp:151:74: warning: narrowing conversion of 'sgt[(- events.std::vector<event>::operator[](((std::vector<event>::size_type)i)).event::stare)].segment::gety()' from 'long double' to 'int' [-Wnarrowing]
151 | auto jos = active.lower_bound({sgt[-events[i].stare].gety(), -1});
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~
roads.cpp:162:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | if(i == events.size() || (events[i + 1].x.first != events[i].x.first || !signs(events[i + 1].stare, events[i].stare))) {
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Failed |
160 ms |
10684 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| 4 |
Correct |
28 ms |
2448 KB |
Output is correct |
| 5 |
Correct |
43 ms |
4568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| 4 |
Correct |
20 ms |
2420 KB |
Output is correct |
| 5 |
Correct |
45 ms |
4612 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
4 ms |
596 KB |
Output is correct |
| 9 |
Failed |
39 ms |
3180 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
468 KB |
Output is correct |
| 4 |
Correct |
22 ms |
2428 KB |
Output is correct |
| 5 |
Correct |
44 ms |
4532 KB |
Output is correct |
| 6 |
Failed |
1 ms |
340 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
2 ms |
468 KB |
Output is correct |
| 5 |
Correct |
19 ms |
2488 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
3 ms |
596 KB |
Output is correct |
| 9 |
Failed |
30 ms |
3240 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Failed |
164 ms |
10624 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
| 3 |
Halted |
0 ms |
0 KB |
- |
