oj.uz

답안 #1109650

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109650 2024-11-07T08:53:11 Z farica 사다리꼴 (balkan11_trapezoid) C++14
38 / 100
 184 ms 56672 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(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

# 결과 실행 시간 메모리 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