oj.uz

Submission #666240

# Submission time Handle Problem Language Result Execution time Memory
666240 2022-11-27T20:52:32 Z Lobo Roads (CEOI20_roads) C++17
100 / 100
 192 ms 19460 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 = 2e5+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]) + (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, int idno) {
    if(no == 0) return mp(0,0);
    // if(xcur == 5) cout << pt[no] << " -- " << y0 << " " << findy(pt[no],xcur) << endl;
    if(findy(pt[no],xcur) <= y0 || pt[no] == idno) {
        auto aux = splitval(rc[no],xcur,y0,idno);
        rc[no] = aux.fr;
        calc(no);
        return mp(no,aux.sc);
    }
    else {
        auto aux = splitval(lc[no],xcur,y0,idno);
        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],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],i);
            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:195:17: warning: unused variable 'rt2' [-Wunused-variable]
  195 |             int rt2 = aux.sc; rt1 = aux.fr;
      |                 ^~~
roads.cpp:100:10: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  100 |     bool ok = 0;
      |          ^~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 68 ms 7112 KB Output is correct

Subtask #2
15.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 2 ms 596 KB Output is correct
4 Correct 9 ms 2604 KB Output is correct
5 Correct 21 ms 4516 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 10 ms 2632 KB Output is correct
5 Correct 24 ms 4420 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 11 ms 2500 KB Output is correct
10 Correct 167 ms 19460 KB Output is correct

Subtask #4
15.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 2 ms 596 KB Output is correct
4 Correct 10 ms 2576 KB Output is correct
5 Correct 19 ms 4428 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 10 ms 2452 KB Output is correct
10 Correct 56 ms 9872 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #5
15.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 340 KB Output is correct
4 Correct 1 ms 556 KB Output is correct
5 Correct 11 ms 2640 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 11 ms 2420 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 11 ms 2504 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 352 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 2 ms 588 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Correct 5 ms 1240 KB Output is correct
23 Correct 5 ms 1240 KB Output is correct
24 Correct 11 ms 1868 KB Output is correct
25 Correct 1 ms 340 KB Output is correct

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 76 ms 7176 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 564 KB Output is correct
6 Correct 15 ms 2512 KB Output is correct
7 Correct 22 ms 4312 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 11 ms 2512 KB Output is correct
12 Correct 167 ms 19284 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 10 ms 2512 KB Output is correct
17 Correct 50 ms 10004 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 468 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 6 ms 1240 KB Output is correct
27 Correct 5 ms 1240 KB Output is correct
28 Correct 11 ms 1876 KB Output is correct
29 Correct 84 ms 10972 KB Output is correct
30 Correct 96 ms 15080 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 109 ms 12600 KB Output is correct
33 Correct 108 ms 12612 KB Output is correct
34 Correct 167 ms 16552 KB Output is correct
35 Correct 192 ms 17196 KB Output is correct
36 Correct 165 ms 18016 KB Output is correct