Submission #1293636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293636		Hamed_Ghaffari	trapezoid (balkan11_trapezoid)	C++20	100 / 100	140 ms	23480 KiB

trapezoid

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

using pii = pair<int, int>;

#define X first
#define Y second
#define mid ((l+r)>>1)
#define lc id<<1
#define rc lc|1
#define all(x) x.begin(), x.end()
#define SZ(x) int(x.size())

const int MXN = 2e5+5;
const int MOD = 30013;

inline pii merge(pii x, pii y) {
    return x.X==y.X ? pii(x.X, (x.Y+y.Y)%MOD) : max(x, y);
}

int N;
pii seg[MXN<<2];
void build(int l=0, int r=N, int id=1) {
    if(r-l == 1) {
        seg[id] = {0, l==0};
        return;
    }
    build(l, mid, lc);
    build(mid, r, rc);
    seg[id] = merge(seg[lc], seg[rc]);
}
void upd(int p, pii x, int l=0, int r=N, int id=1) {
    if(r-l == 1) {
        seg[id] = x;
        return;
    }
    p<mid ? upd(p, x, l, mid, lc) : upd(p, x, mid, r, rc);
    seg[id] = merge(seg[lc], seg[rc]);
}
pii get(int s, int e, int l=0, int r=N, int id=1) {
    if(s<=l && r<=e) return seg[id];
    if(e<=mid) return get(s, e, l, mid, lc);
    if(s>=mid) return get(s, e, mid, r, rc);
    return merge(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}

int n, a[MXN], b[MXN], c[MXN], d[MXN];
pii val[MXN];
vector<int> cx, cy, gt_vec[MXN], up_vec[MXN];

inline int GI(vector<int> &cmp, int x) { return lower_bound(all(cmp), x)-cmp.begin(); }

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    cx.push_back(0);
    cy.push_back(0);
    for(int i=0; i<n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        cx.push_back(a[i]);
        cx.push_back(b[i]);
        cy.push_back(c[i]);
        cy.push_back(d[i]);
    }
    sort(all(cx)); cx.resize(unique(all(cx))-cx.begin());
    sort(all(cy)); cy.resize(unique(all(cy))-cy.begin());
    N = SZ(cy);
    build();
    for(int i=0; i<n; i++) {
        gt_vec[GI(cx, a[i])-1].push_back(i);
        up_vec[GI(cx, b[i])].push_back(i);
    }
    for(int i=0; i<SZ(cx); i++) {
        for(int j : up_vec[i])
            upd(GI(cy, d[j]), val[j]);
        for(int j : gt_vec[i]) {
            pii x = get(0, GI(cy, c[j]));
            val[j] = pii(x.X+1, x.Y);
        }
    }
    cout << seg[1].X << ' ' << seg[1].Y << '\n';
    return 0;
}

• Subtask 1: 100 / 100