Submission #1211478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211478		vanea	trapezoid (balkan11_trapezoid)	C++20	47 / 100	132 ms	15216 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mxN = 2e6+10;
const int MOD = 30013;

vector<int> values;
array<int, 2> st[mxN];
int ans[mxN], ans1[mxN];

int val(int x) {
    return lower_bound(values.begin(), values.end(), x) - values.begin();
}

array<int, 2> comb(array<int, 2> a, array<int, 2> b) {
    array<int, 2> ans = {0, 0};
    if(a[0] == b[0]) {
        ans[0] = a[0];
        ans[1] = (a[1] + b[1])%MOD;
    }
    else if(a[0] > b[0]) {
        ans = a;
    }
    else {
        ans = b;
    }
    ans[0] = max(a[0], b[0]);
    return ans;
}

void upd(int node, int l, int r, int k, int x, int x1) {
    if(l == r && l == k) {
        st[node][0] = x;
        st[node][1] = x1;
        return ;
    }
    if(l > k || r < k) return ;
    int mid = (l+r)/2;
    upd(node*2, l, mid, k, x, x1);
    upd(node*2+1, mid+1, r, k, x, x1);
    st[node] = comb(st[node*2], st[node*2+1]);
}

array<int, 2> qry(int node, int l, int r, int l1, int r1) {
    if(l1 <= l && r <= r1) return st[node];
    if(l1 > r || r1 < l) return {0, 0};
    int mid = (l+r)/2;
    return comb(qry(node*2, l, mid, l1, r1), qry(node*2+1, mid+1, r, l1, r1));
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    vector<array<int, 4>> events;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        events.push_back({a, c, 1, i});
        events.push_back({b, d, -1, i});
        values.push_back(a); values.push_back(c);
        values.push_back(b); values.push_back(d);
    }
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    sort(events.begin(), events.end());
    int mx = 0;
    int cnt = 0;
    for(auto &[x, y, flag, idx] : events) {
        x = val(x); y = val(y);
        if(flag == 1) {
            array<int, 2> now = qry(1, 0, values.size()+1, 0, y);
            now[0]++;
            ans[idx] = now[0];
            ans1[idx] = max(1, now[1]);
            if(now[0] == mx) {
                cnt += now[1];
                cnt %= MOD;
            }
            else {
                mx = now[0];
                cnt = now[1]%MOD;
            }
        }
        else {
            upd(1, 0, values.size()+1, y, ans[idx], ans1[idx]);
        }
    }
    cout << mx << ' ' << cnt;
    return 0;
}

• Subtask 1: 47 / 100