oj.uz

답안 #1109651

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109651 2024-11-07T08:53:39 Z farica 사다리꼴 (balkan11_trapezoid) C++14
67 / 100
 187 ms 31304 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;
    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
67.0 / 100.0

# 결과 실행 시간 메모리 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 760 KB Output is correct
5 Correct 3 ms 848 KB Output is correct
6 Partially correct 4 ms 1360 KB Partially correct
7 Correct 5 ms 1616 KB Output is correct
8 Correct 6 ms 1872 KB Output is correct
9 Partially correct 12 ms 3408 KB Partially correct
10 Correct 21 ms 6620 KB Output is correct
11 Partially correct 29 ms 8016 KB Partially correct
12 Partially correct 79 ms 16720 KB Partially correct
13 Partially correct 90 ms 18768 KB Partially correct
14 Partially correct 115 ms 21872 KB Partially correct
15 Partially correct 147 ms 23640 KB Partially correct
16 Partially correct 160 ms 25160 KB Partially correct
17 Partially correct 153 ms 26696 KB Partially correct
18 Correct 127 ms 28488 KB Output is correct
19 Partially correct 152 ms 29776 KB Partially correct
20 Correct 187 ms 31304 KB Output is correct