Submission #1270852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270852		asdasdqwer	trapezoid (balkan11_trapezoid)	C++20	100 / 100	224 ms	38428 KiB

trapezoid

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

#define int int64_t
#define pii array<int,2>
#define tii array<int,4>

struct Data {
    int maxCount = -1e9;
    int countSubset = -1e9;

    Data(int x, int y) {
        maxCount = x;
        countSubset = y;
    }
};


Data neutral(0, 1);
Data neg(-1, -(int)1e9);


struct Segtree {
    vector<Data> seg;
    int n;

    Segtree(int sz) : n(sz) {
        seg.assign(2*sz, neg);
    }

    Data combine(Data x, Data y) {
        if (x.maxCount > y.maxCount) return x;
        else if (x.maxCount < y.maxCount) return y;
        Data comb(x.maxCount, (x.countSubset + y.countSubset) % 30013);
        return comb;
    }

    void upd(int pos, Data new_data) {
        pos += n;
        seg[pos] = combine(seg[pos], new_data);

        for (;pos > 1;pos>>=1) {
            seg[pos>>1] = combine(seg[pos], seg[(pos^1)]);
        }
    }

    Data query(int l, int r) {
        Data result = neutral;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) result = combine(result, seg[l++]);
            if (r & 1) result = combine(seg[--r], result);
        }

        return result;
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    vector<pair<pii, pii>> vp(n);
    vector<int> v1, v2;
    for (auto &x:vp) {
        cin>>x.first[0]>>x.first[1]>>x.second[0]>>x.second[1];
        v1.push_back(x.first[0]);
        v1.push_back(x.first[1]);
        v2.push_back(x.second[0]);
        v2.push_back(x.second[1]);
    }

    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    v1.erase(unique(v1.begin(), v1.end()), v1.end());
    v2.erase(unique(v2.begin(), v2.end()), v2.end());

    map<int,int> mp1, mp2;
    for (int i=0;i<(int)v1.size();i++) mp1[v1[i]] = i;
    for (int i=0;i<(int)v2.size();i++) mp2[v2[i]] = i;

    for (auto &x:vp) {
        for (int i=0;i<2;i++) {
            x.first[i] = mp1[x.first[i]];
            x.second[i] = mp2[x.second[i]];
        }
    }

    sort(vp.begin(), vp.end());
    Segtree sg(max(v1.size(), v2.size()) + 5);
    priority_queue<tii, vector<tii>, greater<tii>> pq;
    for (auto &x:vp) {
        while (pq.size() && pq.top()[0] <= x.first[0]) {
            tii tmp = pq.top();pq.pop();
            sg.upd(tmp[1], Data(tmp[2], tmp[3]));
        }

        Data ths = sg.query(0, x.second[0]);
        ths.maxCount++;
        pq.push({x.first[1], x.second[1], ths.maxCount, ths.countSubset});
    }

    while (pq.size()) {
        tii tmp = pq.top();pq.pop();
        sg.upd(tmp[1], Data(tmp[2], tmp[3]));
    }

    Data result = sg.query(0, sg.n);
    cout << result.maxCount << " " << result.countSubset << endl;
}

• Subtask 1: 100 / 100