Submission #1109650

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109650	2024-11-07T08:53:11 Z	farica	trapezoid (balkan11_trapezoid)	C++14	38 / 100	184 ms	56672 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] = comb(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(4*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;
    while(true) {
        while(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] = tmp;
                else {
                    ans[x] = query(1, 0, n-1, lb);
                    ++ans[x].ans;
                }
            }
            if(it2 == que.begin()) break;
            --it2;
        }
        for(int x: it->second) {
            update(1, 0, n-1, x, ans[x]);
        }
        if(it == upd.begin()) break;
        --it;
    }
    while(true) {
        for(int x: it2->second) {
            int lb = upper_bound(c.begin(), c.end(), V[x][3]) - c.begin();
            if(lb == n) ans[x] = tmp;
            else {
                ans[x] = query(1, 0, n-1, lb);
                ++ans[x].ans;
            }
        }
        if(it2 == que.begin()) break;
        --it2;
    }
    Node fin = tmp;
    for(int i=0; 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

38.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	Partially correct	1 ms	592 KB	Partially correct
4	Correct	1 ms	592 KB	Output is correct
5	Correct	3 ms	1064 KB	Output is correct
6	Incorrect	4 ms	1232 KB	Output isn't correct
7	Correct	6 ms	1516 KB	Output is correct
8	Runtime error	7 ms	3408 KB	Execution killed with signal 11
9	Runtime error	12 ms	6100 KB	Execution killed with signal 11
10	Runtime error	23 ms	11864 KB	Execution killed with signal 11
11	Partially correct	29 ms	8028 KB	Partially correct
12	Partially correct	74 ms	15652 KB	Partially correct
13	Partially correct	80 ms	16916 KB	Partially correct
14	Runtime error	94 ms	41884 KB	Execution killed with signal 11
15	Runtime error	103 ms	42840 KB	Execution killed with signal 11
16	Runtime error	113 ms	47700 KB	Execution killed with signal 11
17	Runtime error	141 ms	50772 KB	Execution killed with signal 11
18	Runtime error	115 ms	53596 KB	Execution killed with signal 11
19	Runtime error	128 ms	56672 KB	Execution killed with signal 11
20	Correct	184 ms	30804 KB	Output is correct