oj.uz

Submission #51863

# Submission time Handle Problem Language Result Execution time Memory
51863 2018-06-22T09:16:16 Z someone_aa trapezoid (balkan11_trapezoid) C++17
28 / 100
 500 ms 36172 KB 
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
using namespace std;
const int maxn = 100100;
map<int, int> up, down;
ll tree[2*4*maxn];
int upmax, downmax, n;
int dp[maxn];

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

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

ll query(int ql, int qr, int li=0, int ri=downmax, int index=1) {
    if(li > qr || ri < ql) return 0LL;
    else if(li >= ql && ri <= qr) return tree[index];
    else {
        int mid = (li+ri)/2;
        return max(query(ql,qr,li,mid,2*index), query(ql,qr,mid+1,ri,2*index+1));
    }
}

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

int main() {
    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));
    }

    for(int i=1;i<=upmax;i++) {
        for(auto j:events[i]) {
            if(j.second) {
                dp[j.first] = query(0, arr[j.first].c) + 1;
            }
            else update(arr[j.first].d, dp[j.first]);
        }
    }
    int result = 0;
    for(int i=0;i<n;i++) {
        result = max(result, dp[i]);
    }
    cout<<result<<" 0\n";
    return 0;
}

Subtask #1
28.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 4984 KB Partially correct
2 Partially correct 6 ms 5220 KB Partially correct
3 Partially correct 7 ms 5272 KB Partially correct
4 Partially correct 9 ms 5444 KB Partially correct
5 Partially correct 13 ms 5776 KB Partially correct
6 Partially correct 16 ms 6216 KB Partially correct
7 Partially correct 19 ms 6432 KB Partially correct
8 Partially correct 27 ms 6816 KB Partially correct
9 Partially correct 49 ms 8496 KB Partially correct
10 Partially correct 101 ms 11696 KB Partially correct
11 Partially correct 141 ms 13048 KB Partially correct
12 Partially correct 295 ms 20776 KB Partially correct
13 Partially correct 370 ms 23648 KB Partially correct
14 Partially correct 423 ms 28256 KB Partially correct
15 Execution timed out 516 ms 29920 KB Time limit exceeded
16 Execution timed out 667 ms 31204 KB Time limit exceeded
17 Execution timed out 562 ms 32464 KB Time limit exceeded
18 Execution timed out 508 ms 33600 KB Time limit exceeded
19 Execution timed out 667 ms 34532 KB Time limit exceeded
20 Execution timed out 660 ms 36172 KB Time limit exceeded