Submission #1136000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136000		Hamed_Ghaffari	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	377 ms	59908 KiB

fortune_telling2

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

typedef long long       ll;
typedef long double     ld;
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pll;

#define X               first
#define Y               second
#define SZ(x)           int(x.size())
#define all(x)          x.begin(), x.end()
#define mins(a,b)       (a = min(a,b))
#define maxs(a,b)       (a = max(a,b))
#define pb              push_back
#define Mp              make_pair
#define kill(x)         {cout << (x) << '\n'; exit(0);}
#define killt(x)        {cout << (x) << '\n'; return;}
#define lc              id<<1
#define rc              lc|1
#define mid             ((l+r)/2)
mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());

const ll  INF = 1e9 + 23;
const ll  MOD = 1e9 + 7;
const int MXN = 2e5 + 5;
const int MXM = 6e5 + 5;
const int LOG = 23;

int n, k, a[MXN], b[MXN], t[MXN];
vector<int> cmp;

int GI(int x) {
    return lower_bound(all(cmp), x)-cmp.begin();
}

int m, seg[MXM<<2];
void Build_seg(int l=0, int r=m, int id=1) {
    seg[id] = 0;
    if(r-l == 1) return;
    Build_seg(l, mid, lc);
    Build_seg(mid, r, rc);
}
void Upd_seg(int p, int x, int l=0, int r=m, int id=1) {
    if(r-l == 1) {
        seg[id] = x;
        return;
    }
    if(p<mid) Upd_seg(p, x, l, mid, lc);
    else Upd_seg(p, x, mid, r, rc);
    seg[id] = max(seg[lc], seg[rc]);
}
int Get_seg(int s, int e, int l=0, int r=m, int id=1) {
    if(s <= l && r <= e) return seg[id];
    return max(
        (s<mid ? Get_seg(s, e, l, mid, lc) : 0),
        (e>mid ? Get_seg(s, e, mid, r, rc) : 0)
    );
}

vector<int> mrg[MXN<<2];
void merge_sort(int l=1, int r=k+1, int id=1) {
    if(r-l == 1) {
        mrg[id] = {t[l]};
        return;
    }
    merge_sort(l, mid, lc);
    merge_sort(mid, r, rc);
    int i=0, j=0;
    while(i<SZ(mrg[lc]) && j<SZ(mrg[rc]))
        if(mrg[lc][i]<mrg[rc][j]) mrg[id].pb(mrg[lc][i++]);
        else mrg[id].pb(mrg[rc][j++]);
    while(i<SZ(mrg[lc])) mrg[id].pb(mrg[lc][i++]);
    while(j<SZ(mrg[rc])) mrg[id].pb(mrg[rc][j++]);
}
int Get_parity(int s, int e, int x, int l=1, int r=k+1, int id=1) {
    if(s <= l && r <= e) {
        int pos = lower_bound(all(mrg[id]), x)-mrg[id].begin();
        return (SZ(mrg[id])-pos)&1;
    }
    if(e<=mid) return Get_parity(s,e,x, l, mid, lc);
    if(s>=mid) return Get_parity(s,e,x, mid, r, rc);
    return Get_parity(s,e,x, l, mid, lc)^Get_parity(s,e,x, mid, r, rc);
}

void Main() {
    cin >> n >> k;
    for(int i=1; i<=n; i++) {
        cin >> a[i] >> b[i];
        cmp.pb(a[i]);
        cmp.pb(b[i]);
    }
    for(int i=1; i<=k; i++) {
        cin >> t[i];
        cmp.pb(t[i]);
    }
    sort(all(cmp));
    cmp.resize(unique(all(cmp))-cmp.begin());
    m = SZ(cmp);
    for(int i=1; i<=n; i++) {
        a[i] = GI(a[i]);
        b[i] = GI(b[i]);
    }
    Build_seg();
    for(int i=1; i<=k; i++) {
        t[i] = GI(t[i]);
        Upd_seg(t[i], i);
    }
    merge_sort();
    ll ans=0;
    for(int i=1; i<=n; i++) {
        if(a[i] != b[i]) {
            int pos = Get_seg(min(a[i], b[i]), max(a[i], b[i]));
            if(pos) {
                vector<int> vec = {max(a[i], b[i]), min(a[i], b[i])};
                ans += cmp[vec[pos<k && Get_parity(pos+1, k+1, max(a[i], b[i]))]];
            }
            else {
                vector<int> vec = {a[i], b[i]};
                ans += cmp[vec[Get_parity(1, k+1, max(a[i], b[i]))]];
            }
        }
        else ans += cmp[a[i]];
    }
    cout << ans << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while(T--) Main();
    return 0;
}

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