Submission #1156112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156112		vladilius	운세 보기 2 (JOI14_fortune_telling2)	C++20	100 / 100	284 ms	117744 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int A = 1e9;

struct ST{
    struct node{
        node *l, *r;
        int s;
        node(){
            l = r = 0;
            s = 0;
        }
    };
    node *rt;
    void init(){
        rt = new node();
    }
    void add(node *v, int tl, int tr, int x){
        if (tl == tr){
            v -> s += 1;
            return;
        }
        int tm = (tl + tr) / 2;
        if (x <= tm){
            if (!(v -> l)) v -> l = new node();
            add(v -> l, tl, tm, x);
        }
        else {
            if (!(v -> r)) v -> r = new node();
            add(v -> r, tm + 1, tr, x);
        }
        v -> s = 0;
        if (v -> l) v -> s += v -> l -> s;
        if (v -> r) v -> s += v -> r -> s;
    }
    void add(int x){
        add(rt, 1, A, x);
    }
    int get(node *v, int tl, int tr, int l, int r){
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return v -> s;
        int tm = (tl + tr) / 2, out = 0;
        if (v -> l) out += get(v -> l, tl, tm, l, r);
        if (v -> r) out += get(v -> r, tm + 1, tr, l, r);
        return out;
    }
    int get(int x){
        return get(rt, 1, A, x, A);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, k; cin>>n>>k;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i]>>b[i];
    }
    vector<int> t(k + 1);
    vector<pii> all = {{}};
    for (int i = 1; i <= k; i++){
        cin>>t[i];
        all.pb({t[i], i});
    }
    
    sort(all.begin() + 1, all.end());
    vector<int> f(k + 1), p(k + 1);
    for (int i = 1; i <= k; i++){
        f[i] = all[i].ff;
        p[i] = all[i].ss;
    }
    
    vector<int> log(k + 1);
    for (int i = 2; i <= k; i++) log[i] = log[i / 2] + 1;
    const int lg = log[k];
    vector<vector<int>> sp(k + 1, vector<int>(lg + 1));
    for (int i = 1; i <= k; i++) sp[i][0] = p[i];
    for (int j = 1; j <= lg; j++){
        for (int i = 1; i + (1 << j) <= k + 1; i++){
            sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    auto get = [&](int l, int r){
        if (l > r) return 0;
        int k = log[r - l + 1];
        return max(sp[l][k], sp[r - (1 << k) + 1][k]);
    };
    
    vector<int> :: iterator it1, it2;
    
    vector<bool> h(n + 1);
    vector<pii> qs[k + 2];
    ll out = 0;
    for (int i = 1; i <= n; i++){
        if (a[i] == b[i]){
            out += a[i];
            continue;
        }
        if (a[i] < b[i]){
            it1 = lower_bound(f.begin() + 1, f.end(), a[i]);
            it2 = lower_bound(f.begin() + 1, f.end(), b[i]);
            
            int l = (int) (it1 - f.begin()), r = (int) (it2 - f.begin()) - 1, s = get(l, r);
            if (s) h[i] = 1;
            qs[s + 1].pb({i, b[i]});
        }
        else {
            it1 = lower_bound(f.begin() + 1, f.end(), b[i]);
            it2 = lower_bound(f.begin() + 1, f.end(), a[i]);
            
            int l = (int) (it1 - f.begin()), r = (int) (it2 - f.begin()) - 1, s = get(l, r);
            qs[s + 1].pb({i, a[i]});
        }
    }
    
    ST T; T.init();
    for (int i = k + 1; i > 0; i--){
        if (i <= k) T.add(t[i]);
        for (auto [ii, x]: qs[i]){
            int k = T.get(x);
            bool r = (k ^ h[ii]) % 2;
            out += (r) ? b[ii] : a[ii];
        }
    }
    
    cout<<out<<"\n";
}

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65