oj.uz

Submission #51895

# Submission time Handle Problem Language Result Execution time Memory
51895 2018-06-22T13:11:27 Z someone_aa trapezoid (balkan11_trapezoid) C++17
95 / 100
 500 ms 34420 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];

struct node {
public:
    int maxm, cnt;
} bit[4*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;
    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:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
trapezoid.cpp:53: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
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 7 ms 5224 KB Output is correct
3 Correct 8 ms 5304 KB Output is correct
4 Correct 8 ms 5584 KB Output is correct
5 Correct 11 ms 5776 KB Output is correct
6 Correct 14 ms 6072 KB Output is correct
7 Correct 24 ms 6368 KB Output is correct
8 Correct 25 ms 6624 KB Output is correct
9 Correct 51 ms 8120 KB Output is correct
10 Correct 96 ms 11108 KB Output is correct
11 Correct 107 ms 12644 KB Output is correct
12 Correct 228 ms 19812 KB Output is correct
13 Correct 299 ms 22796 KB Output is correct
14 Correct 354 ms 25704 KB Output is correct
15 Correct 414 ms 27204 KB Output is correct
16 Correct 492 ms 28592 KB Output is correct
17 Correct 467 ms 29940 KB Output is correct
18 Correct 413 ms 31480 KB Output is correct
19 Correct 443 ms 32748 KB Output is correct
20 Execution timed out 555 ms 34420 KB Time limit exceeded