Submission #1109657

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109657	2024-11-07T08:59:19 Z	farica	trapezoid (balkan11_trapezoid)	C++14	67 / 100	170 ms	31316 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(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(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;
    }
    tmp.ans = tmp.ways = 1;
    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

67.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	2 ms	592 KB	Output is correct
5	Correct	3 ms	896 KB	Output is correct
6	Partially correct	4 ms	1528 KB	Partially correct
7	Correct	6 ms	1616 KB	Output is correct
8	Correct	7 ms	1884 KB	Output is correct
9	Partially correct	14 ms	3412 KB	Partially correct
10	Correct	24 ms	6472 KB	Output is correct
11	Partially correct	32 ms	8016 KB	Partially correct
12	Partially correct	84 ms	16052 KB	Partially correct
13	Partially correct	111 ms	18760 KB	Partially correct
14	Partially correct	101 ms	21872 KB	Partially correct
15	Partially correct	121 ms	23588 KB	Partially correct
16	Partially correct	136 ms	25164 KB	Partially correct
17	Partially correct	147 ms	26508 KB	Partially correct
18	Correct	108 ms	28240 KB	Output is correct
19	Partially correct	153 ms	29768 KB	Partially correct
20	Correct	170 ms	31316 KB	Output is correct