| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 661562 |
2022-11-26T02:31:02 Z |
Lobo |
Roads (CEOI20_roads) |
C++17 |
|
58 ms |
7044 KB |
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e6+10;
int n, x[maxn], y[maxn];
int cntno, val[maxn], sz[maxn], lc[maxn], rc[maxn], prior[maxn], tr[maxn], pt[maxn];
dbl findy(int i, int xcur) {
if(x[i] == x[i+1]) return y[i];
return ((dbl) y[i+1]-y[i])/((dbl) x[i+1]-x[i])*((dbl) xcur-x[i]) + y[i];
}
int create(int i) {
int no = ++cntno;
pt[no] = i;
tr[i] = no;
val[no] = i;
sz[no] = 1;
prior[no] = rand();
return no;
}
void calc(int no) {
if(no == 0) return;
sz[no] = sz[lc[no]]+1+sz[rc[no]];
}
int merge(int l, int r) {
if(l == 0) return r;
if(r == 0) return l;
if(prior[l] <= prior[r]) {
rc[l] = merge(rc[l],r);
calc(l);
return l;
}
else {
lc[r] = merge(l,lc[r]);
calc(r);
return r;
}
}
pair<int,int> splitval(int no, int xcur, int y0) {
if(no == 0) return mp(0,0);
if(findy(pt[no],xcur) <= y0) {
auto aux = splitval(rc[no],xcur,y0);
rc[no] = aux.fr;
calc(no);
return mp(no,aux.sc);
}
else {
auto aux = splitval(lc[no],xcur,y0);
lc[no] = aux.sc;
calc(no);
return mp(aux.fr,no);
}
}
pair<int,int> splitsz(int no, int szlf) {
if(no == 0) return mp(0,0);
if(sz[lc[no]]+1 <= szlf) {
auto aux = splitsz(rc[no],szlf-sz[lc[no]]-1);
rc[no] = aux.fr;
calc(no);
return mp(no,aux.sc);
}
else {
auto aux = splitsz(lc[no],szlf);
lc[no] = aux.sc;
calc(no);
return mp(aux.fr,no);
}
}
int rightmost(int no) {
if(rc[no] == 0) return no;
return rightmost(rc[no]);
}
void solve() {
cin >> n;
vector<pair<pair<int,int>,pair<int,int>>> pts;
for(int i = 1; i <= 2*n; i+=2) {
cin >> x[i] >> y[i];
cin >> x[i+1] >> y[i+1];
if(mp(x[i],y[i]) > mp(x[i+1],y[i+1])) {
swap(x[i],x[i+1]);
swap(y[i],y[i+1]);
}
pts.pb(mp(mp(x[i],y[i]),mp(i,1)));
pts.pb(mp(mp(x[i+1],y[i+1]),mp(i,-1)));
}
sort(all(pts));
x[2*n+1] = -inf1;
x[2*n+2] = inf1;
y[2*n+1] = -inf1;
y[2*n+2] = -inf1;
vector<int> vec;
vec.pb(2*n+1);
int rt = create(2*n+1);
for(auto X : pts) {
if(X.sc.sc == 1) {
int i = X.sc.fr;
int xcur = X.fr.fr;
pair<int,int> aux;
aux = splitval(rt,xcur,y[i]);
int rt1 = aux.fr; rt = aux.sc;
int rgt = rightmost(rt1);
if(val[rgt] != 2*n+1) {
cout << x[i] << " " << y[i] << " " << x[val[rgt]] << " " << y[val[rgt]] << endl;
}
val[rgt] = i;
int rt2 = create(i);
rt = merge(rt2,rt);
rt = merge(rt1,rt);
// int id = 0; // vec[id] is the last one under i
// for(int j = 0; j < vec.size(); j++) {
// if(findy(vec[j],xcur) <= y[i]) {
// id = j;
// }
// else {
// break;
// }
// }
// if(val[vec[id]] != 2*n+1) {
// cout << x[i] << " " << y[i] << " " << x[val[vec[id]]] << " " << y[val[vec[id]]] << endl;
// }
// val[vec[id]] = i;
// val[i] = i;
// vector<int> newvec;
// for(int j = 0; j <= id; j++) {
// newvec.pb(vec[j]);
// }
// newvec.pb(i);
// for(int j = id+1; j < vec.size(); j++) {
// newvec.pb(vec[j]);
// }
// swap(vec,newvec);
}
else {
int i = X.sc.fr;
int xcur = X.fr.fr;
pair<int,int> aux;
aux = splitval(rt,xcur,y[i+1]);
int rt1 = aux.fr; rt = aux.sc;
aux = splitsz(rt1,sz[rt1]-1);
int rt2 = aux.sc; rt1 = aux.fr;
int rgt = rightmost(rt1);
val[rgt] = i;
rt = merge(rt1,rt);
}
}
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
}
Compilation message
roads.cpp: In function 'void solve()':
roads.cpp:169:17: warning: unused variable 'rt2' [-Wunused-variable]
169 | int rt2 = aux.sc; rt1 = aux.fr;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Failed |
57 ms |
7044 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 |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Failed |
1 ms |
596 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Failed |
1 ms |
596 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Failed |
1 ms |
596 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
Failed |
1 ms |
596 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Failed |
58 ms |
6900 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
| 3 |
Halted |
0 ms |
0 KB |
- |
