Submission #1286947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286947		dex111222333444555	trapezoid (balkan11_trapezoid)	C++20	100 / 100	122 ms	13100 KiB

trapezoid

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define sz(v) ((int)(v).size())
#define all(v) begin((v)), end(v)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define dbg(x) "[" #x " = " << x << "]"
using namespace std;
const int MAXN = 1e5 + 5, infINT = 1e9 + 23737, mod = 30013;
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}

void add(int &a, const int &b){
    a += b;
    if (a >= mod) a -= mod;
}

struct Node{
    int a, b, c, d, id;
    Node(int _a = 0, int _b = 0, int _c = 0, int _d = 0, int _id = 0):
        a(_a), b(_b), c(_c), d(_d), id(_id) {};
};

struct segmentTree{
    int n;
    vector<pair<int, int>> node;
    segmentTree(int _n = 0): n(_n){
        node.assign(n << 2 | 1, {0, 0});
    }
    pair<int, int> combine(const pair<int, int> &left, const pair<int, int> &right){
        pair<int, int> mid;
        mid.fi = max(left.fi, right.fi);
        mid.se = (left.fi == mid.fi ? left.se: 0) + (right.fi == mid.fi ? right.se: 0);
        if (mid.se >= mod) mid.se -= mod;
        return mid;
    }
    void update(int id, int l, int r, int pos, pair<int, int> newNode){
        if (l == r){
            node[id] = {newNode};
            return;
        }
        int m = (l + r) >> 1;
        if (pos <= m) update(id << 1, l, m, pos, newNode);
        else update(id << 1 | 1, m + 1, r, pos, newNode);
        node[id] = combine(node[id << 1], node[id << 1 | 1]);
    }
    void update(int pos, pair<int, int> newNode){
        update(1, 1, n, pos, newNode);
    }
    pair<int, int> get(int id, int l, int r, int u, int v){
        if (l > r || l > v || r < u || u > v) return {0, 0};
        if (l >= u && r <= v) return node[id];
        int m = (l + r) >> 1;
        return combine(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
    }
    pair<int, int> get(int u, int v){
        return get(1, 1, n, u, v);
    }
};

int numNode;
Node val[MAXN], valCopy[MAXN];
pair<int, int> dp[MAXN];
vector<int> compressUp, compressDown;

void input(){
    cin >> numNode;
    for(int i = 1; i <= numNode; i++){
        cin >> val[i].a >> val[i].b >> val[i].c >> val[i].d;
        val[i].id = i;
        compressUp.push_back(val[i].a); compressUp.push_back(val[i].b);
        compressDown.push_back(val[i].c); compressDown.push_back(val[i].d);
    }
}

bool cmpA(const Node &a, const Node &b){
    return a.a > b.a;
}

bool cmpB(const Node &a, const Node &b){
    return a.b > b.b;
}

int getPos(int x, const vector<int> &v){
    return lower_bound(all(v), x) - begin(v) + 1;
}

void solve(){
    sort(all(compressUp)); sort(all(compressDown));
    for(int i = 1; i <= numNode; i++){
        val[i].a = getPos(val[i].a, compressUp);
        val[i].b = getPos(val[i].b, compressUp);
        val[i].c = getPos(val[i].c, compressDown);
        val[i].d = getPos(val[i].d, compressDown);
    }
    for(int i = 1; i <= numNode; i++) valCopy[i] = val[i];
    sort(val + 1, val + 1 + numNode, cmpB);
    sort(valCopy + 1, valCopy + 1 + numNode, cmpA);
    segmentTree myIt((int)compressDown.size() + 1);
    myIt.update((int)compressDown.size() + 1, {0, 1});
    int mxV = 0, mxW = 0, res = 0;
    int j = 1;
    for(int i = 1; i <= numNode; i++){
        while(valCopy[j].a >= val[i].b){
            myIt.update(valCopy[j].c, dp[valCopy[j].id]);
            j++;
        }
        pair<int, int> tmp = myIt.get(val[i].d + 1, (int)compressDown.size() + 1);
        dp[val[i].id] = {tmp.fi + 1, tmp.se};
        if (maximize(mxV, tmp.fi + 1)) res = tmp.se;
        else if (mxV == tmp.fi + 1) add(res, tmp.se);
    }
    cout << mxV << ' ' << res << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("test.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while(t--){
        input();
        solve();
    }
    cerr << TIME << ".s\n";
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100