# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
624730 |
2022-08-08T16:11:31 Z |
Vladth11 |
Roads (CEOI20_roads) |
C++14 |
|
515 ms |
28740 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 =200001;
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;
}
return x.second < a.x.second; /// Nu ar trb sa aiba importanta, dar e necesar sa nu busesc sortarea
if(a.stare != stare) {
return stare > a.stare;
}
}
};
long double swipex;
struct segment {
long double a, b, c, d;
long double 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;
set <pii> already;
bool signs(long double a, long double b) {
if(a < b)
swap(a, b);
if(a > 0 && b < 0)
return 0;
return 1;
}
long double cnt = 0;
void adauga(int a, int b) {
if(a < b)
swap(a, b);
cnt++;
segment first = sgt[a];
segment second = sgt[b];
if(first.a < second.a) {
swap(first, second);
} else if(first.a == second.a) {
if(first.b < second.b) {
swap(first, second);
}
} if(first.a >= second.c) {
cout << (int)first.a << " " << (int)first.b << " " << (int)second.c << " " << (int)second.d << "\n";
return;
}
if(second.a >= first.c) {
cout <<(int)first.c << " " << (int)first.d << " " << (int)second.a << " " << (int)second.b << "\n";
return;
}
cout << (int)first.a << " " << (int)first.b << " " << (int)second.a << " " << (int)second.b << "\n";
}
struct ura {
long double first;
int 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();
}
};
pii up[NMAX], down[NMAX];
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++) {
long double 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;
for(i = 1; i <= n; i++) up[i] = down[i] = (pii){-INF, -INF};
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;
for(long double i = 0; i < events.size(); i++) {
swipex = events[i].x.first;
if(events[i].stare > 0) {
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;
down[indS] = events[i].x;
up[indJ] = events[i].x;
}
active.erase({events[i].x.second, -events[i].stare});
continue;
}
if(events[i].stare > n - 2) continue;
pair <pii, int> x = {events[i].x, events[i].stare};
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;
pii maxim = max(down[indS], up[indJ]);
if(maxim.first != -INF){
cout << x.first.first << " " << x.first.second << " ";
pii doilea;
cout << (int)maxim.first << " " << (int)maxim.second << "\n";
}
up[indJ] = x.first;
down[indS] = x.first;
up[x.second] = x.first;
down[x.second] = x.first;
}
//assert(cnt == n - 3);
return 0;
}
Compilation message
roads.cpp: In function 'int main()':
roads.cpp:121:31: warning: narrowing conversion of 'i' from 'int' to 'long double' [-Wnarrowing]
121 | sgt[i] = {a, b, c, d, i};
| ^
roads.cpp:129:44: warning: narrowing conversion of '(n - 1)' from 'int' to 'long double' [-Wnarrowing]
129 | sgt[n - 1] = {-INF, -INF, INF, -INF, n - 1};
| ~~^~~
roads.cpp:132:36: warning: narrowing conversion of 'n' from 'int' to 'long double' [-Wnarrowing]
132 | sgt[n] = {-INF, INF, INF, INF, n};
| ^
roads.cpp:140:40: warning: narrowing conversion of 'events.std::vector<event>::operator[]((std::vector<event, std::allocator<event> >::size_type)i).event::x.std::pair<int, int>::second' from 'int' to 'long double' [-Wnarrowing]
140 | active.insert({events[i].x.second, events[i].stare});
roads.cpp:152:39: warning: narrowing conversion of 'events.std::vector<event>::operator[]((std::vector<event, std::allocator<event> >::size_type)i).event::x.std::pair<int, int>::second' from 'int' to 'long double' [-Wnarrowing]
152 | active.erase({events[i].x.second, -events[i].stare});
roads.cpp:157:48: warning: narrowing conversion of 'x.std::pair<std::pair<int, int>, int>::first.std::pair<int, int>::second' from 'int' to 'long double' [-Wnarrowing]
157 | auto sus = active.lower_bound({x.first.second, -1});
| ~~~~~~~~^~~~~~
roads.cpp:159:48: warning: narrowing conversion of 'x.std::pair<std::pair<int, int>, int>::first.std::pair<int, int>::second' from 'int' to 'long double' [-Wnarrowing]
159 | auto jos = active.lower_bound({x.first.second, -1}); /// nu vrem daca trece chiar la limita sa-l ignor
| ~~~~~~~~^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
134 ms |
8696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
596 KB |
Output is correct |
4 |
Correct |
25 ms |
2764 KB |
Output is correct |
5 |
Correct |
53 ms |
5124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
596 KB |
Output is correct |
4 |
Correct |
26 ms |
2696 KB |
Output is correct |
5 |
Correct |
51 ms |
5132 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
3 ms |
596 KB |
Output is correct |
9 |
Correct |
31 ms |
2704 KB |
Output is correct |
10 |
Correct |
429 ms |
24424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
596 KB |
Output is correct |
4 |
Correct |
25 ms |
2744 KB |
Output is correct |
5 |
Correct |
50 ms |
5160 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
3 ms |
596 KB |
Output is correct |
9 |
Correct |
28 ms |
2676 KB |
Output is correct |
10 |
Correct |
136 ms |
12360 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
596 KB |
Output is correct |
5 |
Correct |
25 ms |
2776 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
3 ms |
568 KB |
Output is correct |
9 |
Correct |
28 ms |
2708 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
3 ms |
596 KB |
Output is correct |
13 |
Correct |
25 ms |
2772 KB |
Output is correct |
14 |
Correct |
1 ms |
276 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
2 ms |
340 KB |
Output is correct |
20 |
Correct |
3 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
12 ms |
1108 KB |
Output is correct |
23 |
Correct |
12 ms |
1108 KB |
Output is correct |
24 |
Correct |
24 ms |
1996 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
137 ms |
8628 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
3 ms |
596 KB |
Output is correct |
6 |
Correct |
25 ms |
2704 KB |
Output is correct |
7 |
Correct |
53 ms |
5100 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
3 ms |
572 KB |
Output is correct |
11 |
Correct |
29 ms |
2764 KB |
Output is correct |
12 |
Correct |
409 ms |
24360 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
3 ms |
596 KB |
Output is correct |
16 |
Correct |
29 ms |
2680 KB |
Output is correct |
17 |
Correct |
136 ms |
12336 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
3 ms |
512 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
12 ms |
1108 KB |
Output is correct |
27 |
Correct |
12 ms |
1204 KB |
Output is correct |
28 |
Correct |
26 ms |
1932 KB |
Output is correct |
29 |
Correct |
294 ms |
16308 KB |
Output is correct |
30 |
Correct |
367 ms |
22256 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
257 ms |
15712 KB |
Output is correct |
33 |
Correct |
256 ms |
17908 KB |
Output is correct |
34 |
Correct |
357 ms |
23736 KB |
Output is correct |
35 |
Correct |
367 ms |
24688 KB |
Output is correct |
36 |
Correct |
515 ms |
28740 KB |
Output is correct |