oj.uz

Submission #51885

# Submission time Handle Problem Language Result Execution time Memory
51885 2018-06-22T11:27:03 Z someone_aa trapezoid (balkan11_trapezoid) C++17
85 / 100
 500 ms 36604 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) {
    int i;
    for(i=1;i<4*2*maxn;) {
        if(li == ri) {
            break;
        }
        else {
            int mid = (li+ri)/2;
            if(ux <= mid) {
                ri = mid;
                i = i * 2;
            }
            else if(ux > mid) {
                li = mid + 1;
                i = i * 2 + 1;
            }
        }
    }

    index = i;

    while(index > 0) {
        if(index == i) {
            tree[index][0] += value;
            tree[index][1] += valueb;
            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] + 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];
            }
        }
        index /= 2;
    }
}

pii emp;

pii query(int ql, int qr, int li=0, int ri=downmax, int index=1) {
    if(li > qr || ri < ql) return emp;
    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() {
    emp.first = 0;
    emp.second = 0;
    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);
   // cout<<query(0,0).second;
    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]);
        }
    }
    printf("%d %d", result, ways);
    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
trapezoid.cpp:89: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 7 ms 4984 KB Output is correct
2 Correct 7 ms 5260 KB Output is correct
3 Correct 9 ms 5404 KB Output is correct
4 Correct 9 ms 5440 KB Output is correct
5 Correct 12 ms 5660 KB Output is correct
6 Correct 14 ms 6212 KB Output is correct
7 Correct 17 ms 6316 KB Output is correct
8 Correct 25 ms 6768 KB Output is correct
9 Correct 49 ms 8360 KB Output is correct
10 Correct 100 ms 11804 KB Output is correct
11 Correct 107 ms 12980 KB Output is correct
12 Correct 261 ms 21064 KB Output is correct
13 Correct 376 ms 23704 KB Output is correct
14 Correct 394 ms 28412 KB Output is correct
15 Correct 464 ms 29792 KB Output is correct
16 Execution timed out 504 ms 31340 KB Time limit exceeded
17 Execution timed out 545 ms 32692 KB Time limit exceeded
18 Correct 438 ms 34044 KB Output is correct
19 Correct 477 ms 35032 KB Output is correct
20 Execution timed out 572 ms 36604 KB Time limit exceeded