Submission #1354197

#TimeUsernameProblemLanguageResultExecution timeMemory
1354197tasso7trapezoid (balkan11_trapezoid)C++20
40 / 100
325 ms39856 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct segTree{
    vector<int> values;
    int s = 0;

    void u(int n, int l, int r, int i, int x){
        if(i < l || r <= i){return;}
        if(r-l==1){
            values[n] = x;
            return;
        }
        int m = (l+r)/2;
        u(2*n, l, m, i, x); u(2*n+1, m, r, i, x);
        values[n] = max(values[2*n], values[2*n+1]);
    }

    int q(int n, int l, int r, int ql, int qr){
        if(ql <= l && r <= qr){return values[n];}
        if(r <= ql || qr <= l){return 0;}
        int m = (l+r)/2;
        return max(q(2*n, l, m, ql, qr), q(2*n+1, m, r, ql, qr));
    }

    
    void update(int i, int x){
        u(1, 0, s, i, x);
    }
    
    int query(int l, int r){
        return q(1, 0, s, l, r);
    }

    segTree(int n){
        s = 1;
        while(s < n) s <<= 1;
        values.resize(4*s);
        fill(values.begin(), values.end(), 0);
    }
};

int main(){
    int N;
    cin >> N;
    vector<array<ll, 4>> trapezoids(N);
    
    // INPUT AND CHANGE OF VAR
    {set<ll> trapezoids_var_change;
    for(int i = 0; i < N; i++){
        ll a, b, c, d; cin >> a >> b >> c >> d;
        trapezoids[i] = {a,b,c,d};
        trapezoids_var_change.insert(a);
        trapezoids_var_change.insert(b);
        trapezoids_var_change.insert(c);
        trapezoids_var_change.insert(d);
    }

    map<ll,int> idx_changer;
    for(auto a = trapezoids_var_change.begin(); a != trapezoids_var_change.end(); a++){
        idx_changer[*a] = idx_changer.size();
    }
    for(int i = 0; i < N; i++){
        auto[a,b,c,d] = trapezoids[i];
        trapezoids[i] = {idx_changer[a],idx_changer[b],idx_changer[c],idx_changer[d]};
    }}

    sort(trapezoids.begin(), trapezoids.end());

    vector<int> QID(trapezoids.size());
    for(int i = 0; i < QID.size(); i++){QID[i] = i;}
    
    sort(QID.begin(), QID.end(), [&trapezoids](int a, int b){return trapezoids[a][1]<trapezoids[b][1];});

    segTree seg(4*N+1);
    vector<int> para_seg(N, 1);

    int insert_id = N-1;
    int query_id = N-1;
    while(insert_id >= 0 || query_id >= 0){
        // if after inserting insert_id i can still query query_id then i'll insert; otherwise query
        if(query_id == -1 || (insert_id != -1 && (trapezoids[insert_id][0] >= trapezoids[QID[query_id]][1]))){
            // INSERT
            seg.update(trapezoids[insert_id][2], para_seg[insert_id]);
            insert_id--;
        }else{
            // QUERY
            para_seg[QID[query_id]] = seg.query(trapezoids[QID[query_id]][3]+1, 4*N+1) + 1;
            query_id--;
        }
    }


    cout << seg.query(0, 4*N+1) << " 0";

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...