Submission #1109674

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109674	2024-11-07T09:25:37 Z	farica	trapezoid (balkan11_trapezoid)	C++14	73 / 100	176 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);
                    ++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	848 KB	Output is correct
5	Correct	3 ms	1104 KB	Output is correct
6	Partially correct	4 ms	1784 KB	Partially correct
7	Correct	5 ms	1872 KB	Output is correct
8	Correct	7 ms	2384 KB	Output is correct
9	Partially correct	15 ms	4432 KB	Partially correct
10	Correct	22 ms	8440 KB	Output is correct
11	Partially correct	30 ms	10320 KB	Partially correct
12	Partially correct	76 ms	20296 KB	Partially correct
13	Partially correct	91 ms	24392 KB	Partially correct
14	Partially correct	98 ms	28236 KB	Partially correct
15	Partially correct	112 ms	30292 KB	Partially correct
16	Partially correct	128 ms	32328 KB	Partially correct
17	Partially correct	134 ms	34388 KB	Partially correct
18	Correct	110 ms	36380 KB	Output is correct
19	Correct	152 ms	38216 KB	Output is correct
20	Correct	176 ms	40264 KB	Output is correct