oj.uz

답안 #1109664

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109664 2024-11-07T09:08:37 Z farica 사다리꼴 (balkan11_trapezoid) C++14
73 / 100
 177 ms 31220 KB 
#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(!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;
    }
    tmp.ans = tmp.ways = 0;
    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
73.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 4 ms 1016 KB Output is correct
6 Partially correct 5 ms 1360 KB Partially correct
7 Correct 5 ms 1552 KB Output is correct
8 Correct 7 ms 1872 KB Output is correct
9 Partially correct 13 ms 3408 KB Partially correct
10 Correct 26 ms 6480 KB Output is correct
11 Partially correct 32 ms 8016 KB Partially correct
12 Partially correct 67 ms 15772 KB Partially correct
13 Partially correct 95 ms 18760 KB Partially correct
14 Partially correct 132 ms 21868 KB Partially correct
15 Partially correct 124 ms 23564 KB Partially correct
16 Partially correct 162 ms 25160 KB Partially correct
17 Partially correct 160 ms 26552 KB Partially correct
18 Correct 119 ms 28232 KB Output is correct
19 Correct 156 ms 29752 KB Output is correct
20 Correct 177 ms 31220 KB Output is correct