제출 #1071571

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071571		TrinhKhanhDung	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	136 ms	13396 KiB

fortune_telling2

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 21071997)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
   void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
   void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

struct seg{
    vector<int> val;
    int n;

    seg(int _n = 0){
        n = _n;
        val.resize(n * 4 + 3, 0);   
    }

    void upd(int p, int c){
        int i = 1, l = 1, r = n;
        while(l < r){
            int m = (l + r) >> 1;
            if(p <= m){
                i = i * 2;
                r = m;
            }
            else{
                i = i * 2 + 1;
                l = m + 1;
            }
        }
        val[i] = c;
        while(i > 1){
            i >>= 1;
            val[i] = max(val[i * 2], val[i * 2 + 1]);
        }
    }

    int get(int c){
        if(val[1] < c) return -1;
        int i = 1, l = 1, r = n;
        while(l < r){
            int m = (l + r) >> 1;
            if(val[i * 2 + 1] >= c){
                i = i * 2 + 1;
                l = m + 1;
            }
            else{
                i = i * 2;
                r = m;
            }
        }
        return l;
    }
};

struct fen{
    vector<int> tree;
    int n;

    fen(int _n = 0){
        n = _n;
        tree.resize(n + 3, 0);
    }

    void upd(int p, int c){
        while(p <= n){
            tree[p] += c;
            p += p & -p;
        }
    }

    int get(int p){
        int ans = 0;
        while(p > 0){
            ans += tree[p];
            p -= p & -p;
        }
        return ans;
    }
};

const int MAX = 2e5 + 10;

int N, Q;
pair<int, int> a[MAX], q[MAX];

void solve(){
    cin >> N >> Q;
    for(int i=1; i<=N; i++){
        cin >> a[i].fi >> a[i].se;
    }
    for(int i=1; i<=Q; i++){
        cin >> q[i].fi;
        q[i].se = i;
    }
    sort(a + 1, a + N + 1, [&](const pair<int, int> &a, const pair<int, int> &b){return max(a.fi, a.se) > max(b.fi, b.se);});
    sort(q + 1, q + Q + 1, greater<pair<int, int>>());
    fen bit(Q);
    seg it(Q);
    for(int i=1; i<=Q; i++){
        it.upd(q[i].se, q[i].fi);
    }
    int j = 1;
    ll ans = 0;
    for(int i=1; i<=N; i++){
        while(j <= Q && q[j].fi >= max(a[i].fi, a[i].se)){
            bit.upd(q[j].se, 1);
            it.upd(q[j].se, 0);
            j++;
        }
        int p = it.get(min(a[i].fi, a[i].se));
        if(p == -1){
            int c = bit.get(Q);
            if((c + (a[i].fi < a[i].se)) % 2 == 0){
                ans += max(a[i].fi, a[i].se);
            }
            else{
                ans += min(a[i].fi, a[i].se);
            }
        }
        else{
            int c = bit.get(Q) - bit.get(p);
            if(c % 2 == 0){
                ans += max(a[i].fi, a[i].se);
            }
            else{
                ans += min(a[i].fi, a[i].se);
            }
        }
        // cout << ans << ' ';
    }
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("mmgraph.inp", "r", stdin);
//    freopen("mmgraph.out", "w", stdout);

    int t = 1;
   // cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

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