Submission #864277

#	Time	Username	Problem	Language	Result	Execution time	Memory
864277		ngonhatmin	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	464 ms	72940 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for (int i=(a); i>=(b); --i)
#define pb push_back
#define pf push_front
#define mp make_pair
#define TWO(x) (1<<(x))
#define BIT(s,i) (((s)&TWO(i))>0)
#define ON(s,i) (s |= TWO(i))
#define OFF(s,i) (s &= ~TWO(i))
#define FLIP(s,i) (s ^= TWO(i))
#define vvec vector<vector<int>>

struct ngocon{
    int val,lazy;
};

struct point{
    int x,y;
};

typedef pair<int,int> pii;
typedef pair<pii,int> piii;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> pipi;

const int h4[4] = {1,0,-1,0}; /// 4 huong
const int c4[4] = {0,1,0,-1}; /// 4 huong
const int h8[8] = {-1,-1,-1,0,1,1,1,0}; /// 8 huong
const int c8[8] = {-1,0,1,1,1,0,-1,-1}; /// 8 huong
const int cv1[8] = {1,2,2,1,-1,-2,-2,-1}; /// 8 huong quan ma
const int cv2[8] = {-2,-1,1,2,2,1,-1,-2}; /// 8 huong quan ma
const int mod = 1e9 + 7; /// chia du
const int base = 26; /// ma hoa
const int oo = 1e16;
const int N = 2e5 + 2;

int n,k,result;
int a[N],b[N],v[N],f[24*N],d[N],bit[6*N],ans[N];
bool dd[N];
vector <int> nor,vec[N];
unordered_map <int,int> Map;

void compress(){
    FOR(i,1,n){
        nor.pb(a[i]);
        nor.pb(b[i]);
    }
    FOR(i,1,k) nor.pb(v[i]);

    sort(nor.begin(),nor.end());

    //cout << "size: " << nor.size() << ' ' << 2*n + k << '\n';

    int pos;
    FOR(i,1,n){
        pos = lower_bound(nor.begin(),nor.end(),a[i]) - nor.begin() + 1;
        Map[pos] = a[i]; a[i] = pos;
        pos = lower_bound(nor.begin(),nor.end(),b[i]) - nor.begin() + 1;
        Map[pos] = b[i]; b[i] = pos;
    }
    FOR(i,1,k) v[i] = lower_bound(nor.begin(),nor.end(),v[i]) - nor.begin() + 1;
}

void update(int i, int l, int r, int u, int v){
    if (r < u || u < l) return;
    if (l == r){
        f[i] = max(f[i],v);
        return;
    }

    int mid = (l + r) >> 1;

    update(i*2,l,mid,u,v);
    update(i*2+1,mid+1,r,u,v);
    f[i] = max(f[i*2],f[i*2+1]);
}

int query(int i, int l, int r, int u, int v){
    if (r < u || v < l || u > v) return 0;
    if (u <= l && r <= v) return f[i];

    int mid = (l + r) >> 1;

    return max(query(i*2,l,mid,u,v),query(i*2+1,mid+1,r,u,v));
}

void update_bit(int i, int v){
    while (i <= 2*n + k){
        bit[i] += v;
        i += (i & (-i));
    }
}

int query_bit(int i){
    int res = 0;
    while (i > 0){
        res += bit[i];
        i -= (i & (-i));
    }
    return res;

}

//int a1[N],b1[N],ans1[N],ans2[N],result1;
//
//void sub1(){
//    FOR(i,1,n) a1[i] = a[i], b1[i] = b[i];
//
//    FOR(i,1,k){
//        FOR(j,1,n) if (a[j] <= v[i]) swap(a[j],b[j]);
//    }
//
//    FOR(i,1,n){
//        ans1[i] = a[i];
//        result1 += a[i];
//    }
//}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    cin >> n >> k;
    FOR(i,1,n) cin >> a[i] >> b[i];

    FOR(i,1,k) cin >> v[i];

//    sub1();

    compress();

//    FOR(i,1,n) cout << a[i] << ' ' << b[i] << '\n';

//    FOR(i,1,k) cout << v[i] << ' '; cout << '\n';
    FOR(i,1,k){
        update(1,1,2*n+k,v[i],i);
        update_bit(v[i],1);
    }

    FOR(i,1,n){
//        cout << i << ": " << min(a[i],b[i]) << ' ' << max(a[i],b[i]) - 1 << '\n';
        d[i] = query(1,1,2*n + k,min(a[i],b[i]),max(a[i],b[i]) - 1);
        if (d[i] != 0) dd[i] = 1;
        vec[d[i]+1].pb(i);
    }

//    cout << "d: "; FOR(i,1,n) cout << d[i] << ' '; cout << '\n';

    FOR(i,1,k){
        for (auto j : vec[i]) ans[j] = k - i + 1 - query_bit(max(b[j],a[j]) - 1);
        update_bit(v[i],-1);
    }

//    cout << "ans: "; FOR(i,1,n) cout << ans[i] << ' '; cout << '\n';

    FOR(i,1,n){
        a[i] = Map[a[i]];
        b[i] = Map[b[i]];
    }
    FOR(i,1,n){
        if (!dd[i]){
            if (ans[i]%2 == 0) result += a[i];
            else result += b[i];
        }
        else{
            if (a[i] >= b[i]){
                if (ans[i]%2 == 0) result += a[i];
                else result += b[i];
            }
            else{
                if (ans[i]%2 == 0) result += b[i];
                else result += a[i];
            }
        }
    }

//    FOR(i,1,n){
//        if (ans1[i] != ans2[i]) cout << i << ": " << ans1[i] << ' ' << ans2[i] << '\n';
//    }
    cout << result;
}

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