제출 #1036772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1036772		BF001	사다리꼴 (balkan11_trapezoid)	C++17	100 / 100	119 ms	18744 KiB

trapezoid

#include<bits/stdc++.h>
using namespace std;
 
#define N 100005
#define fi first
#define se second

typedef pair<int, int> ii;

int md = 30013;

struct fw{
    int n;
    vector<ii> bit;
    fw(int siz){
        n = siz;
        bit.resize(n + 1, {0, 0});
    }
    void ud(int pos, ii val){
        while (pos <= n){
            if (val.fi > bit[pos].fi) bit[pos].se = val.se;
            else if (val.fi == bit[pos].fi) bit[pos].se = (bit[pos].se + val.se) % md;
            bit[pos].fi = max(bit[pos].fi, val.fi);
            pos += (pos & (-pos));
        }
    }
    ii get(int pos){
        ii rt = {0, 1};
        while (pos >= 1){
            if (bit[pos].fi == rt.fi) rt.se = (rt.se + bit[pos].se) % md;
            else if (rt.fi < bit[pos].fi) rt.se = bit[pos].se;
            rt.fi = max(rt.fi, bit[pos].fi);
            pos -= (pos & (-pos));
        }
        return rt;
    }
};

struct iii{
    int l, r, typ, idx;
    bool operator < (iii& o){
        return l < o.l;
    }
};

int n;
ii res[N];
vector<iii> vec;
vector<int> cy;
map<int, int> dd;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n;
    for (int i = 1; i <= n; i++){
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        cy.push_back(l2);
        cy.push_back(r2);
        vec.push_back({l1, l2, 0, i});
        vec.push_back({r1, r2, 1, i});
    }
 
    sort(cy.begin(), cy.end());
    cy.resize(unique(cy.begin(), cy.end()) - cy.begin());
    sort(vec.begin(), vec.end());

    int pos = 0;
    for (auto x : cy) dd[x] = ++pos;
    fw s1(pos);

    for (auto x : vec){
        int pos = dd[x.r];
        if (x.typ == 0){
            ii dp = s1.get(pos);
            dp.fi++;
            res[x.idx] = dp;
            //cout << " check1 :" << x.idx << " " << dp.fi <<  " " << dp.se << " " << pos << " " << x.l<< "\n";
            continue;
        }
       // cout << " check2 : " << x.idx << " " << pos << " " << res[x.idx].fi << " "<< res[x.idx].se << " " << x.l << "\n";
        s1.ud(pos, res[x.idx]);
    }

    ii ans = s1.get((int) cy.size());

    cout << ans.fi << " " << ans.se;

    return 0;
}

• Subtask 1: 100 / 100