Submission #1058210

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1058210	2024-08-14T08:56:21 Z	fryingduc	trapezoid (balkan11_trapezoid)	C++17	100 / 100	71 ms	13768 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	4444 KB	Output is correct
2	Correct	0 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	2 ms	4700 KB	Output is correct
6	Correct	2 ms	4696 KB	Output is correct
7	Correct	2 ms	4700 KB	Output is correct
8	Correct	4 ms	5112 KB	Output is correct
9	Correct	6 ms	7388 KB	Output is correct
10	Correct	15 ms	7668 KB	Output is correct
11	Correct	14 ms	7900 KB	Output is correct
12	Correct	29 ms	9284 KB	Output is correct
13	Correct	36 ms	9736 KB	Output is correct
14	Correct	53 ms	10140 KB	Output is correct
15	Correct	51 ms	12500 KB	Output is correct
16	Correct	53 ms	12828 KB	Output is correct
17	Correct	65 ms	12896 KB	Output is correct
18	Correct	52 ms	13004 KB	Output is correct
19	Correct	59 ms	13364 KB	Output is correct
20	Correct	71 ms	13768 KB	Output is correct