Submission #66194

#	Time	Username	Problem	Language	Result	Execution time	Memory
66194		reality	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	850 ms	174948 KiB

fortune_telling2

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

const int N = 1e6 + 5;

int a[N],b[N];

int e[20][N];

int t[N];

int SZ;

vector < pii > who[N];

void upd(int i) {
    for (;i;i -= i&(-i))
        t[i] += 1;
}

int que(int i) {
    int ans = 0;
    for (;i <= SZ;i += i&(-i))
        ans += t[i];
    return ans;
}

int how[N];

int main(void) {
    vi w;
    int n,m;
    cin>>n>>m;
    for (int i = 1;i <= n;++i)
        cin>>a[i]>>b[i],w.pb(a[i]),w.pb(b[i]);
    vi h(m);
    for (int i = 1;i <= m;++i) {
        cin>>h[i - 1];
        w.pb(h[i - 1]);
    }
    sort(all(w));
    w.resize(unique(all(w)) - w.begin());
    SZ = w.size();
    int shit = 0;
    for (auto & it : h) {
        it = lower_bound(all(w),it) - w.begin() + 1;
        e[0][it] = ++shit;
    }
    for (int k = 1;(SZ >> k);++k)
        for (int i = 1;i + (1 << k) <= SZ + 1;++i)
            e[k][i] = max(e[k - 1][i],e[k - 1][i + (1 << (k - 1))]);
    for (int i = 1;i <= n;++i) {
        int l = min(a[i],b[i]);
        int r = max(a[i],b[i]);
        int wh = 0;
        l = lower_bound(all(w),l) - w.begin() + 1;
        r = lower_bound(all(w),r) - w.begin() + 1;
        int ind = l;
        for (int t = 20;t >= 0;--t)
            if (ind + (1 << t) <= r)
                smax(wh,e[t][ind]),ind += 1 << t;
        if (wh != 0) {
            how[i] = 1;
            if (a[i] > b[i])
                swap(a[i],b[i]);
        }
        who[wh].pb(mp(i,r));
    }
    for (int i = m;i >= 0;--i) {
        for (auto it : who[i]) {
            how[it.fi] ^= que(it.se) & 1;
        }        
        if (i > 0)
            upd(h[i - 1]);
    }
    ll answer = 0;
    for (int i = 1;i <= n;++i)
        answer += (!how[i] ? a[i] : b[i]);
    cout << answer << '\n';
    return 0;
}

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