oj.uz

Submission #51870

# Submission time Handle Problem Language Result Execution time Memory
51870 2018-06-22T09:39:09 Z someone_aa trapezoid (balkan11_trapezoid) C++17
38 / 100
 500 ms 34392 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 5 ms 4984 KB Partially correct
2 Partially correct 6 ms 5092 KB Partially correct
3 Partially correct 6 ms 5272 KB Partially correct
4 Partially correct 9 ms 5476 KB Partially correct
5 Partially correct 12 ms 5808 KB Partially correct
6 Partially correct 13 ms 6192 KB Partially correct
7 Partially correct 16 ms 6380 KB Partially correct
8 Partially correct 24 ms 6764 KB Partially correct
9 Partially correct 38 ms 8300 KB Partially correct
10 Partially correct 72 ms 11244 KB Partially correct
11 Partially correct 100 ms 12668 KB Partially correct
12 Partially correct 237 ms 19964 KB Partially correct
13 Partially correct 298 ms 22652 KB Partially correct
14 Partially correct 385 ms 26424 KB Partially correct
15 Partially correct 438 ms 27672 KB Partially correct
16 Partially correct 479 ms 29124 KB Partially correct
17 Partially correct 459 ms 30568 KB Partially correct
18 Partially correct 443 ms 31868 KB Partially correct
19 Partially correct 465 ms 32892 KB Partially correct
20 Execution timed out 547 ms 34392 KB Time limit exceeded