Submission #51885

#	Time	Username	Problem	Language	Result	Execution time	Memory
51885		someone_aa	사다리꼴 (balkan11_trapezoid)	C++17	85 / 100	572 ms	36604 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];

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

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