oj.uz

Submission #666234

# Submission time Handle Problem Language Result Execution time Memory
666234 2022-11-27T20:45:26 Z Lobo Roads (CEOI20_roads) C++17
0 / 100
 1000 ms 6596 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;
const dbl eps = 1e-9;
 
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]) + (dbl) y[i];
}

dbl findywtf(int i, int xcur, int wtf) {
    if(x[i] == x[i+1]) return y[i+wtf];
    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(xcur == 5) cout << pt[no] << " -- " << y0 << " " << findy(pt[no],xcur) << endl;
    if(findy(pt[no],xcur)+eps <= y0 && findy(pt[no],xcur)-eps <= 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;
    bool ok = 0;
    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])) ok = 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)));
    }

    for(int i = 1; i <= 2*n; i+= 2) {
        for(int j = 1; j <= 2*n; j+= 2) {
            if(i == j) continue;
            if(x[i+1] < x[j] || x[j+1] < x[i]) continue;
            int x1 = max(x[i],x[j]);
            int x2 = min(x[i+1],x[j+1]);

            if(findywtf(i,x1,0) <= findywtf(j,x1,0) && findywtf(i,x2,1) >= findywtf(j,x2,1)) ok = 1;
        }
    }
    if(ok) {
        cout << -1 << endl;
        return;
    }

 
    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;
            // cout << i << " put " << xcur << endl;
 
            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;
            // cout << i << " tak " << xcur << endl;
 
            pair<int,int> aux;
            aux = splitval(rt,xcur,y[i+1]);
            int rt1 = aux.fr; rt = aux.sc;
            // cout << rt1 << " " << rt << endl;
            aux = splitsz(rt1,sz[rt1]-1);
            int rt2 = aux.sc; rt1 = aux.fr;
            int rgt = rightmost(rt1);
            val[rgt] = i+1;
            rt = merge(rt1,rt);
            // cout << rgt << " " << pt[rgt] << " " << pt[rt] << endl;
        }
    }
}

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:196:17: warning: unused variable 'rt2' [-Wunused-variable]
  196 |             int rt2 = aux.sc; rt1 = aux.fr;
      |                 ^~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 1079 ms 6504 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 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 4 ms 596 KB Output is correct
4 Correct 340 ms 2600 KB Output is correct
5 Execution timed out 1047 ms 3536 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 4 ms 596 KB Output is correct
4 Correct 338 ms 2628 KB Output is correct
5 Execution timed out 1022 ms 3536 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 5 ms 644 KB Output is correct
4 Correct 325 ms 2604 KB Output is correct
5 Execution timed out 1076 ms 3540 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 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 1 ms 468 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 324 ms 2600 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Failed 5 ms 568 KB Condition failed: "pf == Sline.end() || !Cross(S[*pa], S[*pf])"
9 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 1084 ms 6596 KB Time limit exceeded
3 Halted 0 ms 0 KB -