oj.uz

Submission #51866

# Submission time Handle Problem Language Result Execution time Memory
51866 2018-06-22T09:22:08 Z someone_aa trapezoid (balkan11_trapezoid) C++17
38 / 100
 500 ms 34440 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;
int 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
38.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 4984 KB Partially correct
2 Partially correct 7 ms 5220 KB Partially correct
3 Partially correct 7 ms 5528 KB Partially correct
4 Partially correct 9 ms 5548 KB Partially correct
5 Partially correct 11 ms 5764 KB Partially correct
6 Partially correct 14 ms 6172 KB Partially correct
7 Partially correct 18 ms 6572 KB Partially correct
8 Partially correct 23 ms 6860 KB Partially correct
9 Partially correct 41 ms 8284 KB Partially correct
10 Partially correct 80 ms 11228 KB Partially correct
11 Partially correct 113 ms 12508 KB Partially correct
12 Partially correct 247 ms 19980 KB Partially correct
13 Partially correct 322 ms 22672 KB Partially correct
14 Partially correct 381 ms 26256 KB Partially correct
15 Partially correct 462 ms 27772 KB Partially correct
16 Partially correct 465 ms 29096 KB Partially correct
17 Partially correct 498 ms 30444 KB Partially correct
18 Partially correct 421 ms 31756 KB Partially correct
19 Partially correct 456 ms 32940 KB Partially correct
20 Execution timed out 540 ms 34440 KB Time limit exceeded