oj.uz

Submission #51864

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

    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
36.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 5112 KB Partially correct
2 Partially correct 6 ms 5224 KB Partially correct
3 Partially correct 7 ms 5300 KB Partially correct
4 Partially correct 8 ms 5460 KB Partially correct
5 Partially correct 11 ms 5924 KB Partially correct
6 Partially correct 13 ms 6096 KB Partially correct
7 Partially correct 16 ms 6400 KB Partially correct
8 Partially correct 22 ms 6920 KB Partially correct
9 Partially correct 41 ms 8484 KB Partially correct
10 Partially correct 82 ms 11672 KB Partially correct
11 Partially correct 138 ms 12964 KB Partially correct
12 Partially correct 237 ms 20832 KB Partially correct
13 Partially correct 317 ms 23520 KB Partially correct
14 Partially correct 355 ms 28176 KB Partially correct
15 Partially correct 426 ms 29720 KB Partially correct
16 Execution timed out 579 ms 31056 KB Time limit exceeded
17 Partially correct 467 ms 32476 KB Partially correct
18 Partially correct 445 ms 33620 KB Partially correct
19 Partially correct 467 ms 34556 KB Partially correct
20 Execution timed out 550 ms 36256 KB Time limit exceeded