oj.uz

Submission #51887

# Submission time Handle Problem Language Result Execution time Memory
51887 2018-06-22T11:31:08 Z someone_aa trapezoid (balkan11_trapezoid) C++17
85 / 100
 500 ms 36708 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 6 ms 5112 KB Output is correct
2 Correct 6 ms 5224 KB Output is correct
3 Correct 8 ms 5388 KB Output is correct
4 Correct 11 ms 5408 KB Output is correct
5 Correct 13 ms 5632 KB Output is correct
6 Correct 18 ms 6064 KB Output is correct
7 Correct 22 ms 6316 KB Output is correct
8 Correct 30 ms 6700 KB Output is correct
9 Correct 52 ms 8412 KB Output is correct
10 Correct 87 ms 11612 KB Output is correct
11 Correct 124 ms 13084 KB Output is correct
12 Correct 259 ms 20920 KB Output is correct
13 Correct 347 ms 23864 KB Output is correct
14 Correct 405 ms 28524 KB Output is correct
15 Correct 434 ms 30008 KB Output is correct
16 Execution timed out 590 ms 31312 KB Time limit exceeded
17 Execution timed out 557 ms 32636 KB Time limit exceeded
18 Correct 452 ms 34076 KB Output is correct
19 Correct 466 ms 34796 KB Output is correct
20 Execution timed out 605 ms 36708 KB Time limit exceeded