Submission #1109677

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109677	2024-11-07T09:31:15 Z	farica	trapezoid (balkan11_trapezoid)	C++14	100 / 100	169 ms	40264 KB

trapezoid

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MOD = 30013;

struct Node {
    int ans,ways;
};

vector<Node>segm;

Node comb(Node x, Node y) {
    Node fin;
    if(x.ans == y.ans) {
        fin.ans = x.ans;
        fin.ways = (x.ways + y.ways) % MOD;
        return fin;
    } else if(x.ans > y.ans) return x;
    else return y;
}

void update(int pos, int l, int r, int x, Node val) {
    if(l==r) {
        segm[pos] = val;
        return;
    }
    int m = (l+r)/2;
    if(x <= m) update(2*pos+1, l, m, x, val);
    else update(2*pos+2, m+1, r, x, val);
    segm[pos] = comb(segm[2*pos+1], segm[2*pos+2]);
}

Node query(int pos, int l, int r, int L) {
    if(l >= L) return segm[pos];
    int m = (l+r)/2;
    if(m >= L) return comb(query(2*pos+1, l, m, L), segm[2*pos+2]);
    else return query(2*pos+2, m+1, r, L);
}

void solve() {
    int n;
    cin >> n;
    Node tmp;
    tmp.ans = tmp.ways = 0;
    segm.assign(8*n, tmp);
    tmp.ans = tmp.ways = 1;
    map<int,vector<int>>upd, que;
    vector<array<int,4>>V(n);
    vector<int>c(n);
    vector<Node>ans(n, tmp);
    for(int i=0; i<n; ++i) {
        cin >> V[i][1] >> V[i][2] >> V[i][0] >> V[i][3];
        c[i] = V[i][0];
    }
    sort(V.begin(), V.end());
    sort(c.begin(), c.end());
    for(int i=0; i<n; ++i) {
        que[V[i][2]].push_back(i);
        upd[V[i][1]].push_back(i);
    }
    auto it = upd.end(), it2 = que.end();
    --it, --it2;
    bool finish = 0;
    while(true) {
        while(!finish && it->first <= it2->first) {
            for(int x: it2->second) {
                int lb = upper_bound(c.begin(), c.end(), V[x][3]) - c.begin();
                if(lb != n) {
                    ans[x] = query(1, 0, n-1, lb);
                    if(!ans[x].ans) ans[x].ways = 1;
                    ++ans[x].ans;
                }
            }
            if(it2 == que.begin()) {
                finish = 1;
                break;
            }
            --it2;
        }
        for(int x: it->second) {
            update(1, 0, n-1, x, ans[x]);
        }
        if(it == upd.begin()) break;
        --it;
    }
    while(!finish) {
        for(int x: it2->second) {
            int lb = upper_bound(c.begin(), c.end(), V[x][3]) - c.begin();
            if(lb != n) {
                ans[x] = query(1, 0, n-1, lb);
                if(!ans[x].ans) ans[x].ways = 1;
                ++ans[x].ans;
            }
        }
        if(it2 == que.begin()) break;
        --it2;
    }
    Node fin = ans[0];
    for(int i=1; i<n; ++i) {
        if(ans[i].ans == fin.ans) {
            fin.ways = (fin.ways + ans[i].ways) % MOD;
        } else if(ans[i].ans > fin.ans) fin = ans[i];
    }
    cout << fin.ans << " " << fin.ways << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    while(t--)
        solve();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	592 KB	Output is correct
4	Correct	2 ms	848 KB	Output is correct
5	Correct	3 ms	1104 KB	Output is correct
6	Correct	4 ms	1788 KB	Output is correct
7	Correct	5 ms	1872 KB	Output is correct
8	Correct	7 ms	2384 KB	Output is correct
9	Correct	15 ms	4316 KB	Output is correct
10	Correct	24 ms	8436 KB	Output is correct
11	Correct	36 ms	10456 KB	Output is correct
12	Correct	88 ms	20296 KB	Output is correct
13	Correct	93 ms	24396 KB	Output is correct
14	Correct	110 ms	28184 KB	Output is correct
15	Correct	130 ms	30280 KB	Output is correct
16	Correct	160 ms	32328 KB	Output is correct
17	Correct	155 ms	34200 KB	Output is correct
18	Correct	115 ms	36384 KB	Output is correct
19	Correct	154 ms	38300 KB	Output is correct
20	Correct	169 ms	40264 KB	Output is correct