oj.uz

Submission #51862

# Submission time Handle Problem Language Result Execution time Memory
51862 2018-06-22T09:15:42 Z someone_aa trapezoid (balkan11_trapezoid) C++17
0 / 100
 500 ms 60484 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++) {
        cout<<i<<": \n";
        for(auto j:events[i]) {
            cout<<j.first<<" "<<j.second<<"\n";
            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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4984 KB Expected integer, but "1:" found
2 Incorrect 6 ms 5096 KB Expected integer, but "1:" found
3 Incorrect 8 ms 5392 KB Expected integer, but "1:" found
4 Incorrect 10 ms 5656 KB Expected integer, but "1:" found
5 Incorrect 17 ms 6184 KB Expected integer, but "1:" found
6 Incorrect 19 ms 6532 KB Expected integer, but "1:" found
7 Incorrect 22 ms 6916 KB Expected integer, but "1:" found
8 Incorrect 31 ms 7452 KB Expected integer, but "1:" found
9 Incorrect 59 ms 9540 KB Expected integer, but "1:" found
10 Incorrect 117 ms 13488 KB Expected integer, but "1:" found
11 Incorrect 142 ms 15588 KB Expected integer, but "1:" found
12 Incorrect 367 ms 25780 KB Expected integer, but "1:" found
13 Incorrect 430 ms 30364 KB Expected integer, but "1:" found
14 Execution timed out 534 ms 37288 KB Time limit exceeded
15 Execution timed out 565 ms 41092 KB Time limit exceeded
16 Execution timed out 616 ms 44604 KB Time limit exceeded
17 Execution timed out 633 ms 48496 KB Time limit exceeded
18 Execution timed out 637 ms 52324 KB Time limit exceeded
19 Execution timed out 626 ms 55916 KB Time limit exceeded
20 Execution timed out 823 ms 60484 KB Time limit exceeded