Submission #51895

#	Time	Username	Problem	Language	Result	Execution time	Memory
51895		someone_aa	trapezoid (balkan11_trapezoid)	C++17	95 / 100	555 ms	34420 KiB

trapezoid

#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 (stderr)

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 / 100