oj.uz

Submission #51897

# Submission time Handle Problem Language Result Execution time Memory
51897 2018-06-22T13:16:18 Z someone_aa trapezoid (balkan11_trapezoid) C++17
90 / 100
 500 ms 34148 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 upmax, downmax, n;
int dp[maxn];
int dpways[maxn];

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

struct node {
public:
    int maxm, cnt;
} bit[2*maxn];

node mergef(node a, node b) {
    if(a.maxm > b.maxm) return a;
    if(b.maxm > a.maxm) return b;
    a.cnt += b.cnt;
    if(a.cnt > mod)
        a.cnt -= mod;
    return a;
}

node query(int pos) {
    node temp;
    temp.cnt = temp.maxm = 0;
    for(; pos > 0; pos -= pos & (-pos)) {
        temp = mergef(temp, bit[pos]);
    }
    return temp;
}

void update(int pos, node value) {
    for(; pos <= downmax; pos += pos &(-pos)) {
        bit[pos] = mergef(bit[pos],value);
    }
}

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++;
    }
    update(1, {0, 1});
    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;
    int ways = 0;
    for(int i=1;i<=upmax;i++) {
        for(auto j:events[i]) {
            if(j.second) {
                node temp = query(arr[j.first].c);
                dp[j.first] = temp.maxm + 1;
                dpways[j.first] = temp.cnt;
                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:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
trapezoid.cpp:52: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
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5216 KB Output is correct
3 Correct 8 ms 5268 KB Output is correct
4 Correct 8 ms 5440 KB Output is correct
5 Correct 11 ms 5824 KB Output is correct
6 Correct 13 ms 6020 KB Output is correct
7 Correct 17 ms 6456 KB Output is correct
8 Correct 22 ms 6740 KB Output is correct
9 Correct 42 ms 8152 KB Output is correct
10 Correct 78 ms 11032 KB Output is correct
11 Correct 99 ms 12520 KB Output is correct
12 Correct 262 ms 19828 KB Output is correct
13 Correct 284 ms 22756 KB Output is correct
14 Correct 343 ms 25572 KB Output is correct
15 Correct 441 ms 27116 KB Output is correct
16 Execution timed out 553 ms 28552 KB Time limit exceeded
17 Correct 483 ms 29924 KB Output is correct
18 Correct 421 ms 31332 KB Output is correct
19 Correct 463 ms 32684 KB Output is correct
20 Execution timed out 575 ms 34148 KB Time limit exceeded