Submission #51878

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
51878	2018-06-22T10:14:47 Z	someone_aa	trapezoid (balkan11_trapezoid)	C++17	80 / 100	500 ms	36644 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;
        if(tree[index][1] > mod)
            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]);
            if(tree[index][1] > mod) tree[index][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");

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    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];
            if(ways > mod)
                ways %= mod;
        }
    }
    cout<<result<<" "<<ways<<"\n";
    return 0;
}

Subtask #1

80.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4984 KB	Output is correct
2	Correct	6 ms	5092 KB	Output is correct
3	Correct	6 ms	5296 KB	Output is correct
4	Correct	8 ms	5444 KB	Output is correct
5	Correct	10 ms	5696 KB	Output is correct
6	Correct	13 ms	6080 KB	Output is correct
7	Correct	17 ms	6516 KB	Output is correct
8	Correct	23 ms	6868 KB	Output is correct
9	Correct	61 ms	8496 KB	Output is correct
10	Correct	84 ms	11884 KB	Output is correct
11	Correct	109 ms	13108 KB	Output is correct
12	Correct	251 ms	21100 KB	Output is correct
13	Correct	310 ms	23920 KB	Output is correct
14	Correct	389 ms	28544 KB	Output is correct
15	Correct	489 ms	30076 KB	Output is correct
16	Execution timed out	524 ms	31464 KB	Time limit exceeded
17	Execution timed out	544 ms	32724 KB	Time limit exceeded
18	Correct	457 ms	34144 KB	Output is correct
19	Execution timed out	513 ms	34816 KB	Time limit exceeded
20	Execution timed out	608 ms	36644 KB	Time limit exceeded