Submission #1109669

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109669	2024-11-07T09:19:04 Z	farica	trapezoid (balkan11_trapezoid)	C++14	73 / 100	165 ms	31516 KB

trapezoid

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

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);
                    ++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);
                ++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

73.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	592 KB	Output is correct
5	Correct	3 ms	848 KB	Output is correct
6	Partially correct	4 ms	1160 KB	Partially correct
7	Correct	5 ms	1616 KB	Output is correct
8	Correct	6 ms	1872 KB	Output is correct
9	Partially correct	14 ms	3408 KB	Partially correct
10	Correct	30 ms	6480 KB	Output is correct
11	Partially correct	32 ms	8016 KB	Partially correct
12	Partially correct	72 ms	15944 KB	Partially correct
13	Partially correct	96 ms	18760 KB	Partially correct
14	Partially correct	107 ms	22044 KB	Partially correct
15	Partially correct	147 ms	23624 KB	Partially correct
16	Partially correct	126 ms	25076 KB	Partially correct
17	Partially correct	139 ms	27424 KB	Partially correct
18	Correct	109 ms	28236 KB	Output is correct
19	Correct	138 ms	29772 KB	Output is correct
20	Correct	165 ms	31516 KB	Output is correct