Submission #51874

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
51874	2018-06-22T10:06:37 Z	someone_aa	trapezoid (balkan11_trapezoid)	C++17	42 / 100	500 ms	36728 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;
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;
    }
    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];
        }
        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);
        else if(a.first > b.first) return a;
        else return b;
    }
}

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

int main() {
    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];
    }
    cout<<result<<" "<<ways<<"\n";
    return 0;
}

Subtask #1

42.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	7 ms	5092 KB	Output is correct
3	Partially correct	7 ms	5424 KB	Partially correct
4	Partially correct	10 ms	5504 KB	Partially correct
5	Partially correct	14 ms	5824 KB	Partially correct
6	Partially correct	20 ms	6208 KB	Partially correct
7	Partially correct	16 ms	6408 KB	Partially correct
8	Partially correct	22 ms	6976 KB	Partially correct
9	Partially correct	41 ms	8520 KB	Partially correct
10	Partially correct	77 ms	11720 KB	Partially correct
11	Partially correct	93 ms	13020 KB	Partially correct
12	Partially correct	259 ms	21144 KB	Partially correct
13	Partially correct	303 ms	23768 KB	Partially correct
14	Partially correct	380 ms	28436 KB	Partially correct
15	Partially correct	446 ms	30084 KB	Partially correct
16	Partially correct	479 ms	31352 KB	Partially correct
17	Execution timed out	534 ms	32772 KB	Time limit exceeded
18	Partially correct	420 ms	34040 KB	Partially correct
19	Partially correct	464 ms	34924 KB	Partially correct
20	Execution timed out	595 ms	36728 KB	Time limit exceeded