제출 #1083921

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

trapezoid

#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 = {-oo};
    rep(i,0,n){
        rep(j,0,4) cin >> a[i][j];
        swap(a[i][1],a[i][2]);
        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+5);
    fen.update(0,0,1);

    sort(all(a));

    for(auto [a1,b1,a2,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: 100 / 100