Submission #656680

#	Time	Username	Problem	Language	Result	Execution time	Memory
656680		socpite	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	501 ms	31116 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;

const int maxn = 6e5+5;
const ll inf = 1e18;


vector<int> pos;
int st[4*maxn];
pair<int, int> A[maxn];
int B[maxn], os[maxn];
vector<int> qq[maxn];
int sz;

void upd(int l, int r, int k, int id, int val){
    st[id]=val;
    if(l==r)return;
    int mid = (l+r)>>1;
    if(k <= mid)upd(l, mid, k, id<<1, val);
    else upd(mid+1, r, k, id<<1|1, val);
}

int query(int l, int r, int ql, int qr, int id){
    if(ql > qr)return 0;
    if(ql > r || l > qr)return 0;
    if(ql <= l && qr >= r)return st[id];
    else{
        int mid = (l+r)>>1;
        return max(query(l, mid, ql, qr, id<<1), query(mid+1, r, ql, qr, id<<1|1));
    }
}

void add(int l, int r, int k, int id){
    if(l > k)return;
    if(r <= k)st[id]^=1;
    else{
        int mid = (l+r)>>1;
        add(l, mid, k, id<<1);
        add(mid+1, r, k, id<<1|1);
    }
}

int xquery(int l, int r, int k, int id){
    if(l==r)return st[id];
    else{
        int mid = (l+r)>>1;
        if(k <= mid)return xquery(l, mid, k, id<<1)^st[id];
        else return xquery(mid+1, r, k, id<<1|1)^st[id];
    }
}

int n, k;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> A[i].f >> A[i].s;
        pos.push_back(A[i].f);
        pos.push_back(A[i].s);
        if(A[i].f > A[i].s){
            os[i]=1;
            swap(A[i].f, A[i].s);
        }
    }
    for(int i = 1; i <= k; i++){
        cin >> B[i];
        pos.push_back(B[i]);
    }
    pos.push_back(-1);
    sort(pos.begin(), pos.end());
    pos.erase(unique(pos.begin(), pos.end()), pos.end());
    sz = pos.size();
    for(int i = 0; i < n; i++){
        A[i].f = lower_bound(pos.begin(), pos.end(), A[i].f)-pos.begin();
        A[i].s = lower_bound(pos.begin(), pos.end(), A[i].s)-pos.begin();
    }
    for(int i = 1; i <= k; i++){
        B[i] = lower_bound(pos.begin(), pos.end(), B[i])-pos.begin();
        upd(1, sz, B[i], 1, i);
    }
    for(int i = 0; i < n; i++){
        int tmp = query(1, sz, A[i].f, A[i].s-1, 1);
        if(tmp)os[i]=1;
        qq[tmp+1].push_back(i);
    }
    memset(st, 0, sizeof(st));
    for(int i = k; i > 0; i--){
        add(1, sz, B[i], 1);
        for(auto v: qq[i])os[v]^=xquery(1, sz, A[v].s, 1);
    }
    ll ans = 0;
    for(int i = 0; i < n; i++){
        if(os[i])ans+=pos[A[i].s];
        else ans += pos[A[i].f];
    }
    cout << ans << "\n";
}
                

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