Submission #1276958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276958		nanaseyuzuki	운세 보기 2 (JOI14_fortune_telling2)	C++20	0 / 100	2 ms	568 KiB

fortune_telling2

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703 
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 2e5 + 5, inf = 1e9;

int n, k, a[mn], b[mn], c[mn], l[mn], r[mn], tim[mn], ans[mn], pos[mn];
pii e[mn];
vector <int> comp, event[mn];

int bit[mn << 2];

void add(int u, int val){
    while(u <= comp.size()){
        bit[u] += val;
        u += (u & -u);
    }
}

int get(int u){
    int res = 0;
    while(u){
        res += bit[u];
        u -= (u & -u);
    }
    return res;
}

void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
        comp.push_back(a[i]); comp.push_back(b[i]);
        if(a[i] == b[i]){
            l[i] = 0, r[i] = - 1;
            ans[i] = a[i];
        }
        else{
            l[i] = 1, r[i] = k, tim[i] = -1;
        }
    }
    for(int i = 1; i <= k; i++){
        cin >> c[i];
        comp.push_back(c[i]);
    }
    sort(all(comp)); comp.erase(unique(all(comp)), comp.end());
    for(int i = 1; i <= k; i++){
        pos[i] = lower_bound(all(comp), c[i]) - comp.begin() + 1;
    }
    for(int i = 1; i <= n; i++){
        int u = min(a[i], b[i]), v = max(a[i], b[i]);
        u = lower_bound(all(comp), u) - comp.begin() + 1;
        v = lower_bound(all(comp), v) - comp.begin() + 1;
        e[i] = {u, v};
    }

    while(true){
        bool stop = true;
        for(int i = 1; i <= n; i++){
            if(l[i] <= r[i]){
                event[(l[i] + r[i]) >> 1].push_back(i);
                stop = false;
            }
        }
        if(stop) break;
        for(int i = 1; i <= comp.size(); i++) bit[i] = 0;

        for(int i = k; i >= 1; i--){
            add(pos[i], 1);
            for(auto id : event[i]){
                auto [u, v] = e[id];
                int val = get(v - 1) - get(u - 1);
                if(val) l[id] = i + 1;
                else{
                    r[id] = i - 1;
                    tim[id] = i;
                }
            }
            event[i].clear();
        }
    }
    
    for(int i = 1; i <= n; i++){
        event[tim[i]].push_back(i);
    }

    for(int i = 1; i <= comp.size(); i++) bit[i] = 0;
    for(int i = k; i >= 1; i--){
        add(pos[i], 1);
        for(auto id : event[i]){
            auto [u, v] = e[id];
            int val = get(comp.size()) - get(v - 1);
            int q = val % 2;
            if(i > 1) ans[id] = (q ? min(a[id], b[id]) : max(a[id], b[id])); 
            else ans[id] = (q ? b[id] : a[id]);
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i++) res += ans[i];
    cout << res << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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