Submission #46808

#	Time	Username	Problem	Language	Result	Execution time	Memory
46808		tieunhi	trapezoid (balkan11_trapezoid)	C++14	100 / 100	236 ms	34628 KiB

trapezoid

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define N 100005
#define MOD 30013

using namespace std;

int n, a[N], b[N], c[N], d[N], rr[4*N];
int dp[N], dem[N];

void inline ADD(int &a, int b) {a += b; if (a >= MOD) a -= MOD;}
struct event
{
    int u, v, type, id;
    event(int _u=0, int _v=0, int _type=0, int _id=0) : u(_u), v(_v), type(_type), id(_id) {}
    bool operator < (const event &rhs) const {
        return u < rhs.u;
    }
}e[N*2];

struct IntervalTree
{
    int t[N << 4], cnt[N << 4];

    void update(int l, int r, int id, int x, int val, int cntWay)
    {
        if (l > x || r < x) return;
        if (l == r)
        {
            if (val < t[id]) return;
            else if (t[id] == val) ADD(cnt[id], cntWay);
            else cnt[id] = cntWay;
            t[id] = val;
            return;
        }
        int mid = (r + l)/2;
        if (x <= mid) update(l, mid, id*2, x, val, cntWay);
        else update(mid+1, r, id*2+1, x, val, cntWay);
        t[id] = max(t[id*2], t[id*2+1]);
        cnt[id] = 0;
        if (t[id] == t[id*2]) ADD(cnt[id], cnt[id*2]);
        if (t[id] == t[id*2+1]) ADD(cnt[id], cnt[id*2+1]);
    }
    int get(int l, int r, int id, int x, int y)
    {
        if (l > y || r < x) return 0;
        if (l >= x && r <= y) return t[id];
        int mid = (r + l)/2;
        int a = get(l, mid, id*2, x, y);
        int b = get(mid+1, r, id*2+1, x, y);
        return max(a, b);
    }
    int getWay(int l, int r, int id, int x, int y, int val)
    {
        if (l > y || r < x) return 0;
        if (l >= x && r <= y) return (val == t[id])*cnt[id];
        int mid = (r + l)/2;
        int a = getWay(l, mid, id*2, x, y, val);
        int b = getWay(mid+1, r, id*2+1, x, y, val);
        ADD(a, b);
        return a;
    }
}t;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("TRAPEZOID.INP", "r", stdin);
    cin >> n;
    int cur = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        rr[++cur] = a[i]; rr[++cur] = b[i];
        rr[++cur] = c[i]; rr[++cur] = d[i];
    }
    sort(rr+1, rr+cur+1);
    cur = unique(rr+1, rr+cur+1) - rr - 1;
    for (int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(rr+1, rr+cur+1, a[i]) - rr;
        b[i] = lower_bound(rr+1, rr+cur+1, b[i]) - rr;
        c[i] = lower_bound(rr+1, rr+cur+1, c[i]) - rr;
        d[i] = lower_bound(rr+1, rr+cur+1, d[i]) - rr;

    }
    cur = 0;
    for (int i = 1; i <= n; i++)
    {
        e[++cur] = event(a[i], c[i], 0, i);
        e[++cur] = event(b[i], d[i], 1, i);
    }
    sort(e+1, e+cur+1);
    for (int i = 1; i <= cur; i++)
    {
        if (e[i].type == 0)
        {
            dp[e[i].id] = t.get(1, 4*n, 1, 1, e[i].v-1) + 1;
            dem[e[i].id] = max(1, t.getWay(1, 4*n, 1, 1, e[i].v-1, dp[e[i].id] - 1));
        }
        else t.update(1, 4*n, 1, e[i].v, dp[e[i].id], dem[e[i].id]);
    }
    int res = *max_element(dp+1, dp+n+1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (dp[i] == res)
            ADD(ans, dem[i]);
    cout <<res<<" "<<ans;
}

• Subtask 1: 100 / 100