oj.uz

답안 #1098558

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1098558 2024-10-09T15:12:41 Z Icelast 사다리꼴 (balkan11_trapezoid) C++17
100 / 100
 156 ms 51520 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9, mod = 30013;
struct point{
    ll x, y, t, id;
};
struct Node{
    ll lis = 0, cnt = 0;
};
Node merge(Node a, Node b){
    Node res;
    res.lis = max(a.lis, b.lis);
    if(a.lis > b.lis){
        res.cnt = a.cnt;
    }else if(a.lis < b.lis){
        res.cnt = b.cnt;
    }else{
        res.cnt = a.cnt+b.cnt;
    }
    res.cnt %= mod;
    return res;
}
struct SegmentTree{
    int n, N;
    vector<Node> T;
    SegmentTree(int n) : n(n){
        N = 1;
        while(N < n) N*=2;
        T.resize(N*2+1, Node());
    };

    void modify(int i, Node x){
        auto modify = [&](auto self, int node, int low, int high, int i, Node x) -> void{
            if(low == high){
                T[node] = x;
                return;
            }
            int mid = (low+high)/2;
            if(i <= mid){
                self(self, node*2, low, mid, i, x);
            }else{
                self(self, node*2+1, mid+1, high, i, x);
            }
            T[node] = merge(T[node*2], T[node*2+1]);
        };
        modify(modify, 1, 1, N, i, x);
    }
    Node rangeQuery(int l, int r){
        auto rangeQuery = [&](auto self, int node, int low, int high, int l, int r) -> Node{
            if(low > r || l > high) return Node();
            if(low >= l && r >= high) return T[node];
            int mid = (low+high)/2;
            return merge(self(self, node*2, low, mid, l, r), self(self, node*2+1, mid+1, high, l, r));
        };
        return rangeQuery(rangeQuery, 1, 1, N, l, r);
    }
};
struct normalize{
    vector<ll> poi, pot;
    void add(ll x){
        poi.push_back(x);
    }
    void start(){
        sort(poi.begin(), poi.end());
        pot.clear();
        pot.push_back(poi[0]);
        for(int i = 1; i < (int)poi.size(); i++){
            if(poi[i] != poi[i-1]){
                pot.push_back(poi[i]);
            }
        }
    }
    int encode(ll x){
        return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+1;
    }
};
void solve(){
    int n;
    cin >> n;
    vector<vector<point>> a(n+1, vector<point>(2));
    for(int i = 1; i <= n; i++){
        cin >> a[i][0].x >> a[i][1].x >> a[i][0].y >> a[i][1].y;
        a[i][0].t = 0;
        a[i][1].t = 1;
        a[i][0].id = a[i][1].id = i;
    }
    normalize norm;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= 1; j++){
            norm.add(a[i][j].x);
            norm.add(a[i][j].y);
        }
    }
    norm.start();
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= 1; j++){
            a[i][j].x = norm.encode(a[i][j].x);
            a[i][j].y = norm.encode(a[i][j].y);
        }
    }
    int N = norm.pot.size();
    vector<vector<point>> b(N+1);
    for(int i = 1; i <= n; i++){
        b[a[i][0].x].push_back(a[i][0]);
        b[a[i][1].x].push_back(a[i][1]);
    }
    SegmentTree T(N+1);
    vector<Node> f(n+1);
    for(int i = 1; i <= N; i++){
        sort(b[i].begin(), b[i].end(), [&](point a, point b){return a.t < b.t;});
        for(auto it : b[i]){
            if(it.t == 0){
                Node prv = T.rangeQuery(1, it.y);
                f[it.id] = merge({prv.lis+1, prv.cnt}, {1, 1});
            }else{
                T.modify(it.y, f[it.id]);
            }
        }
    }
    Node ans = {0, 0};
    for(int i = 1; i <= n; i++){
        ans = merge(ans, f[i]);
    }
    cout << ans.lis << " " << ans.cnt << "\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 3 ms 1372 KB Output is correct
6 Correct 4 ms 1880 KB Output is correct
7 Correct 4 ms 1884 KB Output is correct
8 Correct 6 ms 2520 KB Output is correct
9 Correct 15 ms 5984 KB Output is correct
10 Correct 23 ms 8576 KB Output is correct
11 Correct 33 ms 13272 KB Output is correct
12 Correct 73 ms 26692 KB Output is correct
13 Correct 94 ms 29844 KB Output is correct
14 Correct 110 ms 45020 KB Output is correct
15 Correct 116 ms 34036 KB Output is correct
16 Correct 137 ms 36352 KB Output is correct
17 Correct 129 ms 46868 KB Output is correct
18 Correct 114 ms 37388 KB Output is correct
19 Correct 148 ms 49952 KB Output is correct
20 Correct 156 ms 51520 KB Output is correct