oj.uz

답안 #1083918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1083918 2024-09-04T14:11:17 Z BLOBVISGOD 사다리꼴 (balkan11_trapezoid) C++17
94 / 100
 110 ms 8996 KB 
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int mod = 30013;

struct fentree{
    struct node{
        int v=0, cnt=0;
        node operator+(node b){
            if (b.v==v) return {v,(cnt+b.cnt)%mod};
            else if (b.v<v) return {v,cnt};
            else return b;
        }
    };

    int n;
    vector<node> a;

    fentree( int N ) : n(N), a(N+1) {}

    auto get(int r){
        node ans = {0,0};
        for(r++; r>0; r-=r&(-r)) ans = ans + a[r];
        return ans; 
    } 

    void update(int at, int v, int ways){
        node u = {v,ways};
        for(at++; at<n; at+=at&(-at)) a[at] = a[at] + u;
    }
};

const int oo = ll(2e9);

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n; cin >> n;

    vector<array<int,4>> a(n+1);
    vi coords;
    rep(i,0,n){
        rep(j,0,4) cin >> a[i][j];
        rep(j,0,4) coords.push_back(a[i][j]);
    }
    coords.push_back(oo);
    a[n] = {oo,oo,oo,oo};

    sort(all(coords));
    coords.erase(unique(all(coords)),end(coords));
    auto ctoi = [&coords](int at) -> int {
        return lower_bound(all(coords),at)-begin(coords);
    };

    for(auto& v : a) rep(i,0,4) v[i] = ctoi(v[i]);
    int m = sz(coords);

    priority_queue<array<int,4>,vector<array<int,4>>,greater<array<int,4>>> pq;
    fentree fen(m);
    fen.update(0,0,1);

    sort(all(a));

    for(auto [a1,a2,b1,b2] : a){
        while (sz(pq) and pq.top()[0]<=a1){
            auto [x,y,v,w] = pq.top();
            pq.pop();
            fen.update(y,v,w);
        }

        auto ret = fen.get(b1);
        pq.push({a2,b2,ret.v+1,ret.cnt});
    }

    assert(sz(pq) == 1);

    cout << pq.top()[2]-1 << ' ' << pq.top()[3] << '\n';
}

Subtask #1
94.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 3 ms 608 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 5 ms 860 KB Output is correct
9 Correct 10 ms 1248 KB Output is correct
10 Correct 17 ms 2084 KB Output is correct
11 Correct 23 ms 2564 KB Output is correct
12 Correct 48 ms 4812 KB Output is correct
13 Correct 65 ms 5584 KB Output is correct
14 Partially correct 76 ms 6724 KB Partially correct
15 Correct 87 ms 6692 KB Output is correct
16 Correct 84 ms 7368 KB Output is correct
17 Correct 93 ms 8136 KB Output is correct
18 Correct 81 ms 7100 KB Output is correct
19 Partially correct 95 ms 8648 KB Partially correct
20 Correct 110 ms 8996 KB Output is correct