Submission #24721

#	Time	Username	Problem	Language	Result	Execution time	Memory
24721		chpipis	trapezoid (balkan11_trapezoid)	C++11	56 / 100	296 ms	65536 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAXN = 1e5 + 5;
const int MOD = 30013;
const int INF = 1e9 + 5;

struct node {
    node *left, *right;
    ii val;
    node(ii v, node *l, node *r) {
        val = v;
        left = l;
        right = r;
    }

    node *ins(int L, int R, int x, ii v);
} *root[MAXN];

node *null = new node(mp(0, 0), NULL, NULL);

ii combine(ii lhs, ii rhs) {
    if (lhs.fi == rhs.fi)
        return mp(lhs.fi, (lhs.se + rhs.se) % MOD);
    return max(lhs, rhs);
}

node* node::ins(int L, int R, int x, ii v) {
    if (L == R)
        return new node(combine(val, v), null, null);
    int mid = (L + R) >> 1;
    /*ii cur = val;
    if (v > cur)
        cur = v;
    else if (v.fi == cur.fi)
        cur.se += v.se, cur.se %= MOD;*/
    if (x <= mid)
        return new node(combine(val, v), left->ins(L, mid, x, v), right);
    else
        return new node(combine(val, v), left, right->ins(mid + 1, R, x, v));
}

ii query(node *p, int L, int R, int i, int j) {
    if (i > R || j < L) return mp(0, 0);

    if (i <= L && j >= R)
        return p->val;

    int mid = (L + R) >> 1;

    return combine(query(p->left, L, mid, i, j), query(p->right, mid + 1, R, i, j));

    /*ii lval = query(p->left, L, mid, i, j);
    ii rval = query(p->right, mid + 1, R, i, j);

    ii ret = mp(0, 0);
    if (lval.fi == rval.fi)
        ret = mp(lval.fi, (lval.se + rval.se) % MOD);
    else
        ret = max(lval, rval);
    return ret;*/
}

int p[MAXN], a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int dp[MAXN], cnt[MAXN];

inline bool comp(int x, int y) {
    if (b[x] == b[y])
        return d[x] < d[y];
    return b[x] < b[y];
}

int getit(int lo, int hi, int x) {
    int res = -1;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (b[p[mid]] < x) {
            res = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return res;
}

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
        p[i] = i;
    }
    sort(p, p + n, comp);

    null->left = null->right = null;

    dp[0] = 1;
    cnt[0] = 1;

    root[0] = null->ins(1, INF, d[0], mp(1, 1));
#if 0
    printf("sorted:\n");
    for (int i = 0; i < n; i++) {
        printf("%d %d %d %d\n", a[p[i]], b[p[i]], c[p[i]], d[p[i]]);
    }
#endif
#if 0
    for (int i = 1; i < n; i++) {
        int pos = p[i];
        cnt[i] = 0;
        dp[i] = 0;
        int what = getit(0, i - 1, a[p[i]]);
        /*swap(a[pos], b[pos]);
        int what = lower_bound(p, p + i, i, comp) - p - 1;
        swap(a[pos], b[pos]);*/
        for (int j = 0; j <= what; j++) {
            if (d[p[j]] < c[pos]) {
                dp[i] = max(dp[i], dp[j]);
            }
        }
        for (int j = 0; j <= what; j++) {
            if (d[p[j]] < c[pos] && dp[i] == dp[j]) {
                cnt[i] = (cnt[i] + cnt[j]) % MOD;
            }
        }
        dp[i]++;
        if (dp[i] == 1) cnt[i] = 1;
    }
#if 0
    for (int i = 0; i < n; i++) {
        printf("%d) dp: %d, cnt: %d\n", i, dp[i], cnt[i]);
    }
#endif
    int mx = *max_element(dp, dp + n), ans = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] == mx) ans = (ans + cnt[i]) % MOD;
    }
    printf("%d %d\n", mx, ans);
#endif
#if 1
    for (int i = 1; i < n; i++) {
        int pos = p[i];
        int what = getit(0, i - 1, a[pos]);
        //swap(a[pos], b[pos]);
        //int what = lower_bound(p, p + i, i, comp) - p - 1;
        //swap(a[pos], b[pos]);

        //printf("for pos %d what is %d\n", pos, what);

        ii cur = query(root[what], 1, INF, 1, c[pos] - 1);
        dp[i] = cur.fi + 1;
        cnt[i] = (cur.se + (dp[i] == 1 ? 1 : 0)) % MOD;

        #if 0
        cur = query(root[i - 1], 1, INF, d[pos], d[pos]);
        if (cur.fi == dp[i])
            cur.se = (cur.se + cnt[i]) % MOD;
        else
            cur = mp(dp[i], cnt[i]);
        #endif
        root[i] = root[i - 1]->ins(1, INF, d[pos], mp(dp[i], cnt[i]));
    }
    ii ans = query(root[n - 1], 1, INF, 1, INF);
    printf("%d %d\n", ans.fi, ans.se);
#endif
    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:139:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
trapezoid.cpp:141:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
                                                         ^

• Subtask 1: 56 / 100