oj.uz

Submission #51865

# Submission time Handle Problem Language Result Execution time Memory
51865 2018-06-22T09:19:42 Z someone_aa trapezoid (balkan11_trapezoid) C++17
36 / 100
 500 ms 36372 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() {
    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));
    }

    int result = 0;
    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;
                result = max(result, dp[j.first]);
            }
            else update(arr[j.first].d, dp[j.first]);
        }
    }
    cout<<result<<" 0\n";
    return 0;
}

Subtask #1
36.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 5292 KB Partially correct
4 Partially correct 8 ms 5524 KB Partially correct
5 Partially correct 13 ms 5800 KB Partially correct
6 Partially correct 13 ms 6216 KB Partially correct
7 Partially correct 23 ms 6436 KB Partially correct
8 Partially correct 21 ms 6892 KB Partially correct
9 Partially correct 47 ms 8496 KB Partially correct
10 Partially correct 76 ms 11856 KB Partially correct
11 Partially correct 93 ms 13000 KB Partially correct
12 Partially correct 265 ms 20896 KB Partially correct
13 Partially correct 294 ms 23600 KB Partially correct
14 Partially correct 358 ms 28320 KB Partially correct
15 Partially correct 479 ms 29696 KB Partially correct
16 Partially correct 496 ms 31076 KB Partially correct
17 Execution timed out 528 ms 32484 KB Time limit exceeded
18 Partially correct 465 ms 33636 KB Partially correct
19 Partially correct 455 ms 34528 KB Partially correct
20 Execution timed out 531 ms 36372 KB Time limit exceeded