# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
577724 |
2022-06-15T08:24:49 Z |
tengiz05 |
Roads (CEOI20_roads) |
C++17 |
|
176 ms |
11444 KB |
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int inf = 1E9;
int Time;
struct Line {
int x, y;
double s;
pair<int, int> l, r;
Line() {}
Line(int x1, int y1, int x2, int y2) {
x = x1;
y = y1;
if (x2 - x1 == 0) {
s = 0;
} else {
s = 1. * (y2 - y1) / (x2 - x1);
}
l = r = {x1, y1};
}
};
double at(const Line x) {
return x.y + (Time - x.x) * x.s;
}
inline bool operator<(const Line &a, const Line &b) {
if (at(a) - at(b) < -1e-10)
return true;
return false;
}
bool bad(const pair<int, int> &x) {
return abs(x.first) == inf;
}
Line p[100005];
struct Info {
int x;
Info(int x) : x(x) {}
};
bool operator<(const Info &a, const Info &b) {
return p[a.x] < p[b.x];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<tuple<int, int, int>> events;
vector<int> X1(n + 2), Y1(n + 2), X2(n + 2), Y2(n + 2);
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);
} else if (x1 == x2 && y1 > y2) {
swap(y1, y2);
}
events.emplace_back(x1, y1, i);
events.emplace_back(x2, y2, -i);
X1[i] = x1;
Y1[i] = y1;
X2[i] = x2;
Y2[i] = y2;
}
sort(events.begin(), events.end());
set<Info> s;
p[0] = Line(-inf, -inf, inf, -inf);
p[n + 1] = Line(-inf, inf, inf, inf);
for (int i = 1; i <= n; i++) {
p[i] = Line(X1[i], Y1[i], X2[i], Y2[i]);
}
s.insert(Info(0));
s.insert(Info(n + 1));
for (auto [x, y, i] : events) {
Time = x;
if (i > 0) {
auto &L = p[prev(s.upper_bound(Info(i)))->x];
auto &R = p[s.upper_bound(Info(i))->x];
if (!bad(L.r)) {
cout << x << " " << y << " " << L.r.first << " " << L.r.second << "\n";
} else if (!bad(R.l)) {
cout << x << " " << y << " " << R.l.first << " " << R.l.second << "\n";
} else {
}
L.r = {x, y};
R.l = {x, y};
s.insert(Info(i));
} else {
i = -i;
auto &L = p[prev(s.lower_bound(Info(i)))->x];
auto &R = p[next(s.lower_bound(Info(i)))->x];
L.r = {x, y};
R.l = {x, y};
s.erase(Info(i));
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
56 ms |
5900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
3 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3540 KB |
Output is correct |
4 |
Correct |
12 ms |
4192 KB |
Output is correct |
5 |
Correct |
23 ms |
4876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
3 ms |
3540 KB |
Output is correct |
4 |
Correct |
11 ms |
4220 KB |
Output is correct |
5 |
Correct |
22 ms |
4952 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
3 ms |
3540 KB |
Output is correct |
9 |
Correct |
13 ms |
4176 KB |
Output is correct |
10 |
Correct |
176 ms |
10376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3412 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
4 ms |
3540 KB |
Output is correct |
4 |
Correct |
12 ms |
4176 KB |
Output is correct |
5 |
Correct |
24 ms |
4932 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
3 ms |
3412 KB |
Output is correct |
8 |
Correct |
3 ms |
3540 KB |
Output is correct |
9 |
Correct |
14 ms |
4176 KB |
Output is correct |
10 |
Correct |
62 ms |
6984 KB |
Output is correct |
11 |
Correct |
2 ms |
3412 KB |
Output is correct |
12 |
Correct |
2 ms |
3412 KB |
Output is correct |
13 |
Correct |
2 ms |
3412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
3 ms |
3412 KB |
Output is correct |
4 |
Correct |
3 ms |
3516 KB |
Output is correct |
5 |
Correct |
14 ms |
4232 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
3 ms |
3540 KB |
Output is correct |
9 |
Correct |
12 ms |
4176 KB |
Output is correct |
10 |
Correct |
2 ms |
3412 KB |
Output is correct |
11 |
Correct |
3 ms |
3412 KB |
Output is correct |
12 |
Correct |
4 ms |
3540 KB |
Output is correct |
13 |
Correct |
14 ms |
4176 KB |
Output is correct |
14 |
Correct |
2 ms |
3412 KB |
Output is correct |
15 |
Correct |
2 ms |
3412 KB |
Output is correct |
16 |
Correct |
2 ms |
3412 KB |
Output is correct |
17 |
Correct |
2 ms |
3412 KB |
Output is correct |
18 |
Correct |
2 ms |
3412 KB |
Output is correct |
19 |
Correct |
3 ms |
3412 KB |
Output is correct |
20 |
Correct |
3 ms |
3412 KB |
Output is correct |
21 |
Correct |
2 ms |
3412 KB |
Output is correct |
22 |
Correct |
8 ms |
3668 KB |
Output is correct |
23 |
Correct |
8 ms |
3796 KB |
Output is correct |
24 |
Correct |
13 ms |
4060 KB |
Output is correct |
25 |
Correct |
2 ms |
3412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
53 ms |
6020 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
3 ms |
3540 KB |
Output is correct |
6 |
Correct |
11 ms |
4240 KB |
Output is correct |
7 |
Correct |
21 ms |
4972 KB |
Output is correct |
8 |
Correct |
2 ms |
3412 KB |
Output is correct |
9 |
Correct |
3 ms |
3412 KB |
Output is correct |
10 |
Correct |
4 ms |
3540 KB |
Output is correct |
11 |
Correct |
12 ms |
4240 KB |
Output is correct |
12 |
Correct |
161 ms |
10384 KB |
Output is correct |
13 |
Correct |
2 ms |
3412 KB |
Output is correct |
14 |
Correct |
2 ms |
3384 KB |
Output is correct |
15 |
Correct |
3 ms |
3540 KB |
Output is correct |
16 |
Correct |
11 ms |
4216 KB |
Output is correct |
17 |
Correct |
70 ms |
6984 KB |
Output is correct |
18 |
Correct |
2 ms |
3412 KB |
Output is correct |
19 |
Correct |
2 ms |
3412 KB |
Output is correct |
20 |
Correct |
2 ms |
3412 KB |
Output is correct |
21 |
Correct |
2 ms |
3412 KB |
Output is correct |
22 |
Correct |
3 ms |
3412 KB |
Output is correct |
23 |
Correct |
2 ms |
3412 KB |
Output is correct |
24 |
Correct |
3 ms |
3412 KB |
Output is correct |
25 |
Correct |
2 ms |
3412 KB |
Output is correct |
26 |
Correct |
6 ms |
3668 KB |
Output is correct |
27 |
Correct |
6 ms |
3788 KB |
Output is correct |
28 |
Correct |
11 ms |
4052 KB |
Output is correct |
29 |
Correct |
81 ms |
8236 KB |
Output is correct |
30 |
Correct |
111 ms |
10264 KB |
Output is correct |
31 |
Correct |
2 ms |
3412 KB |
Output is correct |
32 |
Correct |
106 ms |
8124 KB |
Output is correct |
33 |
Correct |
118 ms |
8236 KB |
Output is correct |
34 |
Correct |
150 ms |
9752 KB |
Output is correct |
35 |
Correct |
140 ms |
9948 KB |
Output is correct |
36 |
Correct |
146 ms |
11444 KB |
Output is correct |