oj.uz

Submission #51881

# Submission time Handle Problem Language Result Execution time Memory
51881 2018-06-22T10:51:03 Z someone_aa trapezoid (balkan11_trapezoid) C++17
85 / 100
 500 ms 36732 KB 
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn = 100100;
const ll mod = 30013;
map<int, int> up, down;
int tree[2*4*maxn][2];
int upmax, downmax, n;
int dp[maxn];
int dpways[maxn];

struct trapez {
public:
    int a, b, c, d;
} arr[maxn];

void update(int ux, int value, int valueb, int li=0, int ri=downmax, int index=1) {
    if(li==ri) {
        tree[index][0] += value;
        tree[index][1] += valueb;
        if(tree[index][1] > mod)
            tree[index][1] -= mod;
    }
    else {
        int mid = (li+ri)/2;
        if(ux <= mid) update(ux, value, valueb, li, mid, 2*index);
        else if(ux > mid) update(ux, value, valueb, mid+1, ri, 2*index+1);

        if(tree[2*index][0] == tree[2*index+1][0]) {
            tree[index][0] = tree[2*index][0];
            tree[index][1] = (tree[2*index][1] + tree[2*index+1][1]);
            if(tree[index][1] > mod) tree[index][1] -= mod;
        }
        else if(tree[2*index][0] > tree[2*index+1][0]) {
            tree[index][0] = tree[2*index][0];
            tree[index][1] = tree[2*index][1];
        }
        else {
            tree[index][0] = tree[2*index+1][0];
            tree[index][1] = tree[2*index+1][1];
        }
    }
}

pii query(int ql, int qr, int li=0, int ri=downmax, int index=1) {
    if(li > qr || ri < ql) return make_pair(0, 0);
    else if(li >= ql && ri <= qr) return make_pair(tree[index][0], tree[index][1]);
    else {
        int mid = (li+ri)/2;
        pii a = query(ql,qr,li,mid,2*index);
        pii b = query(ql,qr,mid+1,ri,2*index+1);

        if(a.first == b.first) return make_pair(a.first, (a.second+b.second)%mod);
        else if(a.first > b.first) return a;
        else return b;
    }
}

vector<pair<int, bool> > events[2*maxn];

int main() {
    scanf("%d", &n);
    for(int i=0;i<n;i++) {
        scanf("%d %d %d %d", &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));
    }

    update(0,0,1);
    int result = 0;
    int ways = 0;
    for(int i=1;i<=upmax;i++) {
        for(auto j:events[i]) {
            if(j.second) {
                pii temp = query(0, arr[j.first].c);
                dp[j.first] = temp.first + 1;
                dpways[j.first] = temp.second;
                if(dp[j.first] > result) {
                    result = dp[j.first];
                    ways = dpways[j.first];
                }
                else if(dp[j.first] == result) {
                    ways += dpways[j.first];
                    if(ways > mod) ways-=mod;
                }
            }
            else update(arr[j.first].d, dp[j.first], dpways[j.first]);
        }
    }
    cout<<result<<" "<<ways<<"\n";
    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
trapezoid.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &arr[i].a, &arr[i].b, &arr[i].c, &arr[i].d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5092 KB Output is correct
3 Correct 7 ms 5424 KB Output is correct
4 Correct 8 ms 5508 KB Output is correct
5 Correct 11 ms 5824 KB Output is correct
6 Correct 13 ms 6208 KB Output is correct
7 Correct 16 ms 6560 KB Output is correct
8 Correct 23 ms 6884 KB Output is correct
9 Correct 44 ms 8548 KB Output is correct
10 Correct 79 ms 11748 KB Output is correct
11 Correct 112 ms 13080 KB Output is correct
12 Correct 252 ms 21096 KB Output is correct
13 Correct 310 ms 23848 KB Output is correct
14 Correct 394 ms 28516 KB Output is correct
15 Execution timed out 504 ms 30016 KB Time limit exceeded
16 Execution timed out 540 ms 31332 KB Time limit exceeded
17 Correct 490 ms 32900 KB Output is correct
18 Correct 466 ms 33984 KB Output is correct
19 Correct 473 ms 34788 KB Output is correct
20 Execution timed out 550 ms 36732 KB Time limit exceeded