Submission #348952

#	Time	Username	Problem	Language	Result	Execution time	Memory
348952		parsabahrami	trapezoid (balkan11_trapezoid)	C++17	100 / 100	168 ms	24152 KiB

trapezoid

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 2e5 + 10, MOD = 30013;
int dp[N], pd[N], A[N], B[N], C[N], D[N], n; pii fen[N];
vector<int> vec[2][N], cl, cr;

pii operator+(pii x, pii y) {
    if (x.F > y.F) return x;
    if (x.F < y.F) return y;
    return {x.F, (x.S + y.S) % MOD};
}

void upd(int pos, pii x) {
    for (pos++; pos < N; pos += pos & -pos) fen[pos] = fen[pos] + x;
}

pii get(int pos) {
    pii ret = {0, 0};
    for (pos++; pos; pos -= pos & -pos) ret = ret + fen[pos];
    return ret;
}

int id(int x, vector<int> &y) {
    return lower_bound(y.begin(), y.end(), x) - y.begin();
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
        cl.push_back(A[i]); cl.push_back(B[i]);
        cr.push_back(C[i]); cr.push_back(D[i]);
    }
    sort(cl.begin(), cl.end());
    sort(cr.begin(), cr.end());
    cl.resize(unique(cl.begin(), cl.end()) - cl.begin());
    cr.resize(unique(cr.begin(), cr.end()) - cr.begin());
    for (int i = 1; i <= n; i++) {
        A[i] = id(A[i], cl);
        B[i] = id(B[i], cl);
        C[i] = id(C[i], cr);
        D[i] = id(D[i], cr);
        vec[0][A[i]].push_back(i);
        vec[1][B[i]].push_back(i);
    }
    for (int i = 0; i < SZ(cl); i++) {
        for (int &j : vec[0][i]) {
            tie(dp[j], pd[j]) = get(C[j] - 1);
            dp[j]++;
            if (!pd[j]) pd[j] = 1;
        }
        for (int &j : vec[1][i]) {
            upd(D[j], {dp[j], pd[j]});
        }
    }
    pii ret = {0, 0};
    for (int i = 1; i <= n; i++) {
        ret = ret + pii(dp[i], pd[i]);
    }
    printf("%d %d\n", ret.F, ret.S);
    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
trapezoid.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |         scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100