Submission #108901

#	Time	Username	Problem	Language	Result	Execution time	Memory
108901		someone_aa	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	22 ms	19328 KiB

fortune_telling2

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define P pair<ll,ll>
using namespace std;
const int maxn = 200100;
ll tree[4*maxn], n, q;
ll a[maxn], b[maxn];
P t[maxn], tt[maxn];
vector<ll>tree_v[4*maxn];

void build(int li=0, int ri=q-1, int index=1) {
    for(int i=li;i<=ri;i++) {
        tree_v[index].pb(tt[i].first);
    }
    sort(tree_v[index].begin(), tree_v[index].end());

    if(li == ri) {
        tree[index] = t[li].second;
    }
    else {
        int mid = (li + ri) / 2;
        build(li,mid,2*index);
        build(mid+1,ri,2*index+1);
        tree[index] = max(tree[2*index], tree[2*index+1]);
    }
}

ll find_ind(int ql, int qr, int li=0, int ri=q-1, int index=1) {
    if(qr < ql) return -1;
    if(li > qr || ri < ql) return -1;
    else if(li >= ql && ri <= qr) return tree[index];
    else {
        int mid = (li + ri) / 2;
        return max(find_ind(ql,qr,li,mid,2*index), find_ind(ql,qr,mid+1,ri,2*index+1));
    }
}

// returns count of numbers in range [ql, qr] greater or equal to qval
ll query(int ql, int qr, ll qval, int li=0, int ri=q-1, int index=1) {
    if(li > qr || ri < ql) return 0;
    else if(li >= ql && ri <= qr) {
        if(tree_v[index].size() == 0) return 0;
        if(tree_v[index].back() < qval) return 0;

        int ind = tree_v[index].size() - 1;
        for(int cekor=tree_v[ind].size()/2;cekor>0;cekor/=2) {
            while(ind-cekor>=0 && tree_v[index][ind-cekor] >= qval) ind -= cekor;
        }
        return tree_v[index].size() - ind;
    }
    else {
        int mid = (li + ri) / 2;
        return query(ql,qr,qval,li,mid,2*index) + query(ql,qr,qval,mid+1,ri,2*index+1);
    }
}

int main() {
    cin>>n>>q;
    for(int i=1;i<=n;i++) {
        cin>>a[i]>>b[i];
    }
    ll x;
    for(int i=0;i<q;i++) {
        cin>>t[i].first;
        t[i].second = i;
        tt[i] = t[i];
    }

    sort(t, t+q);
    build();

    ll result = 0LL;
    for(int i=1;i<=n;i++) {
        ll li = min(a[i], b[i]);
        ll ri = max(a[i], b[i]);

        ll ind = lower_bound(t, t+q, mp(li, -1LL)) - t;
        ll ind2 = lower_bound(t, t+q, mp(ri, -1LL)) - t;

        ll last_ind = find_ind(ind, ind2-1);

        bool to_swap = false;
        if(last_ind == -1) {
            // count twos in whole array
            ll cnt = query(0, q, ri);
            to_swap = cnt % 2;
        }
        else {
            // count twos in range [last_ind,
            ll cnt = query(last_ind, q, ri);
            to_swap = cnt % 2;
        }

        bool state = false;
        if(a[i] > b[i]) state = false;
        else state = true;

        state |= to_swap;

        if(state) result += li;
        else result += ri;
    }
    cout<<result<<"\n";
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:64:8: warning: unused variable 'x' [-Wunused-variable]
     ll x;
        ^

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