oj.uz

답안 #1036772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1036772 2024-07-27T16:52:40 Z BF001 사다리꼴 (balkan11_trapezoid) C++17
100 / 100
 119 ms 18744 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 3 ms 1116 KB Output is correct
8 Correct 5 ms 1372 KB Output is correct
9 Correct 10 ms 2136 KB Output is correct
10 Correct 18 ms 3924 KB Output is correct
11 Correct 24 ms 4840 KB Output is correct
12 Correct 56 ms 9540 KB Output is correct
13 Correct 67 ms 11336 KB Output is correct
14 Correct 83 ms 13368 KB Output is correct
15 Correct 87 ms 14136 KB Output is correct
16 Correct 96 ms 15016 KB Output is correct
17 Correct 100 ms 15932 KB Output is correct
18 Correct 84 ms 16956 KB Output is correct
19 Correct 110 ms 17668 KB Output is correct
20 Correct 119 ms 18744 KB Output is correct