oj.uz

답안 #506244

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
506244 2022-01-11T23:18:23 Z colossal_pepe 운세 보기 2 (JOI14_fortune_telling2) C++17
0 / 100
 1 ms 1228 KB 
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
using namespace __gnu_pbds;
 
#define pow2(p) (1 << (p))
 
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
             tree_order_statistics_node_update> ordered_set;
 
int n, k;
vector<int> a, b, t, flips;
 
void makePancakes() {
    vector<int> t_sorted = t;
    sort(t_sorted.begin(), t_sorted.end());
    for (int i = 0; i < n; i++) {
        flips[i] += t_sorted.end() -
                    lower_bound(t_sorted.begin(), t_sorted.end(), max(a[i], b[i]));
    }
}
 
void adjustFlips() {
    vector<pair<int, int>> tp(k);
    for (int i = 0; i < k; i++) {
        tp[i].first = t[i];
        tp[i].second = i;
    }
    sort(tp.begin(), tp.end());
    int st[k][20];
    memset(st, 0, sizeof(st));
    for (int i = 0; i < k; i++) {
        st[i][0] = tp[i].second;
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i + pow2(j) - 1 < n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + pow2(j - 1)][j - 1]);
        }
    }
    int log2[200005];
    log2[1] = 0;
    for (int i = 2; i < 20; i++) {
        log2[i] = log2[i / 2] + 1;
    }
    vector<pair<int, int>> p(n);
    for (int i = 0; i < n; i++) {
        p[i].second = i;
        int l =
            lower_bound(tp.begin(), tp.end(), make_pair(min(a[i], b[i]), -1)) - tp.begin();
        int r =
            lower_bound(tp.begin(), tp.end(), make_pair(max(a[i], b[i]), -1)) - tp.begin();
        if (l == r) {
            p[i].first = k;
            continue;
        }
        flips[i] += (b[i] > a[i]);
        int len = r - l, j = log2[r - l];
        p[i].first = max(st[l][j], st[l + len - pow2(j)][j]);
    }
    sort(p.begin(), p.end());
    int ti = 0, pi = 0;
    ordered_set os;
    while (ti < k) {
        os.insert({t[ti], ti});
        while (pi < n and p[pi].first == ti) {
            flips[p[pi].second] -= os.size() - os.order_of_key({max(a[p[pi].second], b[p[pi].second]), -1});
            pi++;
        }
        ti++;
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    a.resize(n), b.resize(n), flips.resize(n);
    t.resize(k);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    for (int i = 0; i < k; i++) {
        cin >> t[i];
    }
    makePancakes();
    adjustFlips();
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        if (flips[i] % 2) ans += b[i];
        else ans += a[i];
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -