Submission #1058206

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1058206	2024-08-14T08:55:39 Z	fryingduc	trapezoid (balkan11_trapezoid)	C++17	43 / 100	62 ms	16500 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 = 2023;
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

43.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	4444 KB	Output is correct
2	Partially correct	0 ms	4444 KB	Partially correct
3	Partially correct	1 ms	4568 KB	Partially correct
4	Partially correct	1 ms	4444 KB	Partially correct
5	Partially correct	1 ms	4700 KB	Partially correct
6	Partially correct	2 ms	4700 KB	Partially correct
7	Partially correct	2 ms	4956 KB	Partially correct
8	Partially correct	3 ms	4956 KB	Partially correct
9	Partially correct	6 ms	7392 KB	Partially correct
10	Partially correct	11 ms	8328 KB	Partially correct
11	Partially correct	14 ms	8724 KB	Partially correct
12	Partially correct	34 ms	10444 KB	Partially correct
13	Partially correct	35 ms	11224 KB	Partially correct
14	Partially correct	42 ms	12184 KB	Partially correct
15	Partially correct	46 ms	14536 KB	Partially correct
16	Partially correct	50 ms	14804 KB	Partially correct
17	Partially correct	51 ms	15300 KB	Partially correct
18	Partially correct	51 ms	15564 KB	Partially correct
19	Partially correct	54 ms	15816 KB	Partially correct
20	Partially correct	62 ms	16500 KB	Partially correct