Submission #1108234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108234		Mike_Vu	trapezoid (balkan11_trapezoid)	C++14	100 / 100	119 ms	10204 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

namespace modulofunc{
    const int mod = 30013;
    int add(int x, int y) {
        ll temp = x+y;
        if (temp >= mod) temp -= mod;
        return temp;
    }
    int sub(int x, int y) {
        ll temp = x-y;
        if (temp < 0) temp += mod;
        return temp;
    }
    void addt(int &x, int y) {
        x = add(x, y);
    }
    void subt(int &x, int y) {
        y = sub(x, y);
    }
    int mul(int x, int y) {
        return 1LL*x*y%mod;
    }
}
using namespace modulofunc;


struct SMT{
    int trsz;
    vector<int> tr, cou;
    void init(int n = 0) {
        trsz=  1;
        while (trsz < n) trsz <<= 1;
        tr.assign(trsz<<1, 0);
        cou.assign(trsz<<1, 0);
    }
    void update(int k, int x, int cnt){
        k += trsz-1;
        if (maximize(tr[k], x)) cou[k] = cnt;
        k >>= 1;
        while (k > 0) {
            if (maximize(tr[k], x)) cou[k] = cnt;
            else {
                cou[k] = 0;
                if (tr[k] == tr[k<<1]) {
                    addt(cou[k], cou[(k<<1)]);
                }
                if (tr[k] == tr[(k<<1)|1]) {
                    addt(cou[k], cou[(k<<1)|1]);
                }
            }
            k >>= 1;
        }
    }
    int query(int l, int r, int &cnt){
        if (l > r) return 0;
        int res = 0;
        cnt = 0;
        l += trsz - 1;
        r += trsz - 1;
        while (l <= r){
            if (l&1) {
                if (maximize(res, tr[l])) cnt = cou[l];
                else if (res == tr[l]) addt(cnt, cou[l]);
                l++;
            }
            if ((r^1)&1) {
                if (maximize(res, tr[r])) cnt = cou[r];
                else if (res == tr[r]) addt(cnt, cou[r]);
                r--;
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

struct item{
    int a, b, c, d;
    item(int _a, int _b, int _c, int _d) {
        a = _a;
        b = _b;
        c = _c;
        d = _d;
    }
};

const int maxn = 1e5+5;
int n, ans = 0, dp[maxn], cou[maxn];
vector<item> v;
vector<int> id;
SMT tr;

void nen() {
    vector<int> v1, v2;
    for (int i = 1; i <= n; i++) {
        v1.pb(v[i].a);
        v1.pb(v[i].b);
        v2.pb(v[i].c);
        v2.pb(v[i].d);
    }
    sort(v1.begin(), v1.end());
    v1.erase(unique(v1.begin(), v1.end()), v1.end());
    sort(v2.begin(), v2.end());
    v2.erase(unique(v2.begin(), v2.end()), v2.end());
    for (int i = 1; i <= n; i++) {
        v[i].a = lower_bound(v1.begin(), v1.end(), v[i].a)-v1.begin()+1;
        v[i].b = lower_bound(v1.begin(), v1.end(), v[i].b)-v1.begin()+1;
        v[i].c = lower_bound(v2.begin(), v2.end(), v[i].c)-v2.begin()+1;
        v[i].d = lower_bound(v2.begin(), v2.end(), v[i].d)-v2.begin()+1;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> n;
    //fill-in
    v.pb(item(0, 0, 0, 0));
    for (int i = 1; i <= n; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        v.pb(item(a, b, c, d));
        id.pb(i);
    }
    nen();
    sort(v.begin(), v.end(), [&](item a, item b){return a.b<b.b;});
    sort(id.begin(), id.end(), [&](int a, int b){return v[a].a < v[b].a;});
    tr.init(maxn*2);
    memset(dp, 0, sizeof(dp));
    fill(cou+1, cou+n+1, 1);
    int j = 0;
    for (int pos : id) {
        while (j+1 <= n && v[j+1].b < v[pos].a) {
            ++j;
//            cout << "update\n";
//            cout << v[j].a << ' ' << v[j].b << ' ' << v[j].c << ' ' << v[j].d << "\n";
//            cout << "values: " << dp[j] << ' ' << cou[j] << "\n";
            tr.update(v[j].d, dp[j], cou[j]);
        }
        int cnt;
        dp[pos] = tr.query(1, v[pos].c-1, cnt)+1;
        if (dp[pos] == 1) cou[pos] = 1;
        else cou[pos] = cnt;
        maximize(ans, dp[pos]);
//        cout << "query\n";
//        cout << v[pos].a << ' ' << v[pos].b << ' ' << v[pos].c << ' ' << v[pos].d << "\n";
//        cout << "values: " << dp[pos] << ' ' << cou[pos] << "\n";
    }
    cout << ans << ' ';
    int couans = 0;
    for (int i= 1; i <= n; i++) {
        if (dp[i] == ans) addt(couans, cou[i]);
    }
    cout << couans;
}
/*
7
1 3 1 9
4 7 2 8
11 15 4 12
10 12 15 19
16 23 16 22
20 22 13 25
30 31 30 31
*/

• Subtask 1: 100 / 100