Submission #1058210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058210		fryingduc	trapezoid (balkan11_trapezoid)	C++17	100 / 100	71 ms	13768 KiB

trapezoid

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)     
#endif

#define int long long

const int maxn = 3e5+5;
const int mod = 30013;
int n, f[maxn], g[maxn];

struct Data{
    int l, r, x, y;
    bool operator < (const Data &o){
        return x < o.x;
    }
} a[maxn];

struct Fenwick{
    #define gb(x) (x) & (-x)
    int n;
    vector<pair<int, int>> bit;
    void init(int sz){
        n = sz;
        bit.resize(n + 2, {0, 0});
    }
    void update(int x, int val, int cnt){
        for(int i = x; i <= n; i += gb(i)){
            if(bit[i].first < val){
                bit[i] = {val, cnt % mod};
            }
            else if(bit[i].first == val){
                bit[i].second += cnt;
                bit[i].second %= mod;
            }
        }
    }
    pair<int, int> get(int x){
        int ans = 0, cnt = 0;
        for(int i = x; i; i -= gb(i)){
            if(ans < bit[i].first){
                ans = bit[i].first, cnt = bit[i].second;
            }
            else if(ans == bit[i].first){
                cnt += bit[i].second;
            }
            cnt %= mod;
        }
        return {ans, cnt % mod};
    }
} fen;

void solve(){
    cin >> n;
    vector<int> v;
    v.push_back(0);
    for(int i = 1; i <= n; ++i){
        cin >> a[i].l >> a[i].r >> a[i].x >> a[i].y;
        v.push_back(a[i].l);
        v.push_back(a[i].r);
    }
    sort(v.begin(), v.end());
    fen.init((int)v.size() + 2);
    for(int i = 1; i <= n; ++i){
        a[i].l = lower_bound(v.begin(), v.end(), a[i].l) - v.begin() + 1;
        a[i].r = lower_bound(v.begin(), v.end(), a[i].r) - v.begin() + 1;
    }
    sort(a + 1, a + n + 1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    fen.update(1, 0, 1);
    for(int i = 1; i <= n; ++i){
        while(!pq.empty() and pq.top().first < a[i].x){
            int adu = pq.top().second;
            fen.update(a[adu].r, f[adu], g[adu]);
            pq.pop();
        }
        pair<int, int> nhoe = fen.get(a[i].l - 1);
        f[i] = nhoe.first + 1, g[i] = nhoe.second;
//        debug(i, f[i], g[i]);
        pq.push({a[i].y, i});
    }
    int ans = 0, pos = 0;
    for(int i = 1; i <= n; ++i){
        if(ans < f[i]){
            ans = f[i];
            pos = g[i] % mod;
//            debug(ans, f[i], g[i]);
        }
        else if(ans == f[i]){
            pos = (pos + g[i]) % mod;
        }
    }
    cout << ans << " " << pos % mod;  
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
//    freopen("in", "r", stdin);

    int test = 1;
    // cin >> test;
    for(int i = 1; i <= test; i++){
      // cout << "Case " << "#" << i << ": "; 
      solve();
    }

    return 0;
}

• Subtask 1: 100 / 100