Submission #147155

#	Time	Username	Problem	Language	Result	Execution time	Memory
147155		jh05013	운세 보기 2 (JOI14_fortune_telling2)	C++17	100 / 100	1323 ms	47404 KiB

fortune_telling2

#include <bits/stdc++.h>
#define dbgv(v) {for(auto x:v)cout<<x<<' ';cout<<'\n';}
#define entire(v) v.begin(),v.end()
typedef long long ll;
using namespace std;
void OJize(){
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    #ifdef jh
    freopen("input.txt", "r", stdin);
    #endif
}

// 0-indexed
template <typename T>
struct Segtree{
    T id = -2147483647;
    T combine(T a, T b){
        return max(a, b);
    }
    
    int n; vector<T> arr;
    Segtree(int sz): n{1} {
        while(n < sz) n<<=1;
        arr.resize(n*2);
    }
    void update(int i, T val){
        for(arr[i+=n] = val; i > 1; i/= 2) arr[i/2] = combine(arr[i], arr[i^1]);
    }
    T query(int l, int r){
        T resl = id, resr = id;
        for(l+= n, r+= n+1; l < r; l/= 2, r/= 2){
            if(l&1) resl = combine(resl, arr[l++]);
            if(r&1) resr = combine(resr, arr[--r]);
        }
        return combine(resl, resr);
    }
};

// 0-indexed
template <typename T>
struct Fenwick{
    int n; vector<T> arr;
    Fenwick(int n): n{n}, arr{vector<T>(n)} {}
    void construct(vector<T>& A){
        for(int i=0; i<n; i++) arr[i] = A[i];
        for(int i=0; i<n; i++) if((i|(i+1)) < n) arr[i|(i+1)]+= arr[i];
    }
    void update(int i, T val){
        while(i < n) arr[i]+= val, i |= i+1;
    }
    T getsum(int i){
        T res = 0;
        while(i >= 0) res+= arr[i], i = (i&(i+1))-1;
        return res;
    }
    T intersum(int i, int j){
        return i? (getsum(j) - getsum(i-1)) : getsum(j);
    }
};

/*
 * Treat each card individually, wlog a<b. (if a=b, trivial; if a>b, flip once.)
 * each operation x is either
 *   1. x < a: never flip
 *   2. a <= x < b: set to "flipped"
 *   3. b <= x: always flip
 * so we need to find the last occurrence of a<=x<b, then count the number of b<=x after that point.
 * last occurrence: max segtree
 * count b<=x after some point: offline sum segtree
 */

int main(){OJize();
    // Input and compression
    int n, k; cin>>n>>k;
    vector<tuple<int, int, int>> card(n); // max(a,b), a, b, index 0-i
    vector<pair<int, int>> query(k);           // x, index 1-i
    map<int, int> com;
    for(int i=0; i<n; i++){
        int a, b; cin>>a>>b;
        card[i] = make_tuple(-max(a, b), a, b);
        com[a] = com[b] = 0;
    }
    for(int i=0; i<k; i++) cin>>query[i].first, query[i].second = i+1, com[query[i].first] = 0;
    int i = 0;
    for(auto it = com.begin(); it != com.end(); it++) it->second = i++;
    sort(entire(card));
    sort(entire(query));
    
    // Segtrees
    Segtree<int> maxst(com.size()); // last index of query x, compressed, 1-i
    for(auto &xi: query) maxst.update(com[xi.first], xi.second);
    Fenwick<int> F(k+1); // current occurrence of large query at i, 1-i
    
    // Computation
    ll ans = 0;
    int CI = k-1;
    for(auto& tup: card){
        // Get compressed a and b
        int mab, ra, rb; tie(mab,ra,rb) = tup;
        if(ra == rb){ans+= ra; continue;}
        int a = com[ra], b = com[rb];
        if(a > b) swap(a, b);
        
        // Update large-number queries
        while(CI >= 0 && query[CI].first >= -mab){
            F.update(query[CI].second, 1);
            CI--;
        }
        
        // Count flips
        int last = maxst.query(a, b-1), flip = F.intersum(last, F.n-1) % 2, val;
        if(last == 0) val = flip? rb : ra;
        else val = ((ra>rb)^flip)? ra : rb;
        ans+= val;
        //cout <<ra<<' '<<rb<<" -> "<<a<<' '<<b<<" -> "<<last<<" last; "<<flip<<" flips; "<<val<<'\n';
    }
    
    cout << ans;
}

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