Submission #51876

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
51876	2018-06-22T10:11:05 Z	someone_aa	trapezoid (balkan11_trapezoid)	C++17	70 / 100	500 ms	36636 KB

trapezoid

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn = 100100;
const ll mod = 30013;
map<int, int> up, down;
int tree[2*4*maxn][2];
int upmax, downmax, n;
int dp[maxn];
int dpways[maxn];

struct trapez {
public:
    int a, b, c, d;
} arr[maxn];

void update(int ux, ll value, ll valueb, int li=0, int ri=downmax, int index=1) {
    if(li==ri) {
        tree[index][0] += value;
        tree[index][1] += valueb;
        tree[index][1] %= mod;
    }
    else {
        int mid = (li+ri)/2;
        if(ux <= mid) update(ux, value, valueb, li, mid, 2*index);
        else if(ux > mid) update(ux, value, valueb, mid+1, ri, 2*index+1);

        if(tree[2*index][0] == tree[2*index+1][0]) {
            tree[index][0] = tree[2*index][0];
            tree[index][1] = (tree[2*index][1] + tree[2*index+1][1])%mod;
        }
        else if(tree[2*index][0] > tree[2*index+1][0]) {
            tree[index][0] = tree[2*index][0];
            tree[index][1] = tree[2*index][1];
        }
        else {
            tree[index][0] = tree[2*index+1][0];
            tree[index][1] = tree[2*index+1][1];
        }
    }
}

pii query(int ql, int qr, int li=0, int ri=downmax, int index=1) {
    if(li > qr || ri < ql) return make_pair(0, 0);
    else if(li >= ql && ri <= qr) return make_pair(tree[index][0], tree[index][1]);
    else {
        int mid = (li+ri)/2;
        pii a = query(ql,qr,li,mid,2*index);
        pii b = query(ql,qr,mid+1,ri,2*index+1);

        if(a.first == b.first) return make_pair(a.first, (a.second+b.second)%mod);
        else if(a.first > b.first) return a;
        else return b;
    }
}

vector<pair<int, bool> > events[2*maxn];

int main() {
    //ifstream fin;
    //fin.open("input.txt");

    cin>>n;
    for(int i=0;i<n;i++) {
        cin>>arr[i].a>>arr[i].b>>arr[i].c>>arr[i].d;
        up[arr[i].a] = 1;
        up[arr[i].b] = 1;
        down[arr[i].c] = 1;
        down[arr[i].d] = 1;
    }

    upmax = downmax = 1;
    for(auto i:up) {
        up[i.first] = upmax++;
    }
    for(auto i:down) {
        down[i.first] = downmax++;
    }

    for(int i=0;i<n;i++) {
        arr[i].a = up[arr[i].a];
        arr[i].b = up[arr[i].b];
        arr[i].c = down[arr[i].c];
        arr[i].d = down[arr[i].d];

        events[arr[i].a].push_back(make_pair(i, true));
        events[arr[i].b].push_back(make_pair(i, false));
    }

    update(0,0,1);
    for(int i=1;i<=upmax;i++) {
        for(auto j:events[i]) {
            if(j.second) {
                pii temp = query(0, arr[j.first].c);
                dp[j.first] = temp.first + 1;
                dpways[j.first] = temp.second;
            }
            else update(arr[j.first].d, dp[j.first], dpways[j.first]);
        }
    }

    int result = 0;
    int ways = 0;
    for(int i=0;i<n;i++) {
        if(dp[i] > result) {
            result = dp[i];
            ways = dpways[i];
        }
        else if(dp[i] == result) {
            ways += dpways[i];
            ways %= mod;
        }
    }
    cout<<result<<" "<<ways<<"\n";
    return 0;
}

Subtask #1

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	5112 KB	Output is correct
2	Correct	7 ms	5112 KB	Output is correct
3	Correct	7 ms	5300 KB	Output is correct
4	Correct	8 ms	5504 KB	Output is correct
5	Correct	15 ms	5760 KB	Output is correct
6	Correct	19 ms	6304 KB	Output is correct
7	Correct	21 ms	6520 KB	Output is correct
8	Correct	28 ms	6884 KB	Output is correct
9	Correct	79 ms	8548 KB	Output is correct
10	Correct	127 ms	11812 KB	Output is correct
11	Correct	134 ms	13156 KB	Output is correct
12	Correct	335 ms	21040 KB	Output is correct
13	Correct	363 ms	23868 KB	Output is correct
14	Correct	436 ms	28580 KB	Output is correct
15	Execution timed out	522 ms	30052 KB	Time limit exceeded
16	Execution timed out	724 ms	31312 KB	Time limit exceeded
17	Execution timed out	633 ms	32752 KB	Time limit exceeded
18	Execution timed out	558 ms	34132 KB	Time limit exceeded
19	Execution timed out	599 ms	35012 KB	Time limit exceeded
20	Execution timed out	756 ms	36636 KB	Time limit exceeded