제출 #1354191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1354191		tasso7	사다리꼴 (balkan11_trapezoid)	C++20	12 / 100	313 ms	39816 KiB

trapezoid

#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(2*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());

    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[query_id][1]))){
            // INSERT
            
            seg.update(trapezoids[insert_id][2], para_seg[insert_id]);
            insert_id--;
        }else{
            // QUERY
            para_seg[query_id] = seg.query(trapezoids[query_id][3]+1, 4*N+1) + 1;
            query_id--;
        }
    }

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

    return 0;
}

• 서브태스크 1: 12 / 100