Submission #1083918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083918		BLOBVISGOD	trapezoid (balkan11_trapezoid)	C++17	94 / 100	110 ms	8996 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;
    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 / 100