Submission #147939

#	Time	Username	Problem	Language	Result	Execution time	Memory
147939		evpipis	trapezoid (balkan11_trapezoid)	C++11	100 / 100	299 ms	19544 KiB

trapezoid

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;

const int len = 1e5+5, mod = 30013;
ii tree[8*len], dp[len];
vector<int> vec;
priority_queue<ii, vector<ii>, greater<ii> > pq;
map<int, int> mym;

struct trapezoid{
    int a1, b1, a2, b2;

    bool operator < (const trapezoid &other) const{
        return (a1 < other.a1);
    }
} tra[len];

ii join(ii a, ii b){
    if (a.fi == b.fi)
        return mp(a.fi, (a.se+b.se)%mod);
    return max(a, b);
}

void upd(int p, int l, int r, int i, ii v){
    tree[p] = join(tree[p], v);

    if (l == r)
        return;

    int mid = (l+r)/2;
    if (i <= mid)
        upd(2*p, l, mid, i, v);
    else
        upd(2*p+1, mid+1, r, i, v);
}

ii ask(int p, int l, int r, int i, int j){
    if (r < i || j < l)
        return mp(0, 0);
    if (i <= l && r <= j)
        return tree[p];

    int mid = (l+r)/2;
    return join(ask(2*p, l, mid, i, j), ask(2*p+1, mid+1, r, i, j));
}

int main(){
    int n, m = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d %d %d %d", &tra[i].a1, &tra[i].b1, &tra[i].a2, &tra[i].b2);
        vec.pb(tra[i].a2);
        vec.pb(tra[i].b2);
    }

    sort(vec.begin(), vec.end());
    for (int i = 0; i < 2*n; i++)
        mym[vec[i]] = ++m;

    upd(1, 0, m, 0, mp(0, 1));

    sort(tra, tra+n);
    for (int i = 0; i < n; i++){
        while (!pq.empty()){
            int id = pq.top().se, rig = pq.top().fi;

            if (rig > tra[i].a1)
                break;

            pq.pop();
            upd(1, 0, m, mym[tra[id].b2], dp[id]);
        }

        dp[i] = ask(1, 0, m, 0, mym[tra[i].a2]);
        dp[i].fi++;

        pq.push(mp(tra[i].b1, i));
    }

    ii ans = mp(0, 0);
    for (int i = 0; i < n; i++)
        ans = join(ans, dp[i]);

    printf("%d %d\n", ans.fi, ans.se);
    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
trapezoid.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &tra[i].a1, &tra[i].b1, &tra[i].a2, &tra[i].b2);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100