Submission #1174070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174070		MPG	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	604 ms	88068 KiB

fortune_telling2

#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("O1, O2, O3, Ofast")
#pragma GCC optimization ("trapv")
#pragma GCC optimization ("sse, sse2, sse3, sse4, sse4.1, sse4.2, avx, avx2")



#include <bits/stdc++.h>
using namespace std;
typedef long long                           ll;
#define                                     max_heap priority_queue<ll>
#define                                     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>>
//#define                                     min_heap priority_queue<ll, vector<ll>, greater<ll>>
#define                                     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define                                     filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout); 
#define                                     endl '\n'
#define                                     md(a) (a % mod + mod) % mod
//cout << setprecision(5) << f;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll const maxn = 6e5 + 123;
ll const inf = 2e18;
ll const loG = 23;
//ll const mod = 1e9 + 7;
ll const mod = 998244353;
ll const sq = 350;
ll power(ll a, ll b, ll mod){return b ? 1LL * power(1LL * a * a % mod, b / 2, mod) * (b % 2 ? a : 1) % mod : 1;}


ll n, k, arr[maxn][2], brr[maxn], chi[maxn], sz = 2;
vector <ll> seg[2], adad[maxn], comp;
vector <pair <pair <ll, ll>, ll>> qu[maxn];
bool av[maxn];

void setter1(ll i, ll val, ll x, ll lx, ll rx){
    if (rx - lx == 1){
        seg[0][x] = max(seg[0][x], val);
        return;
    }
    ll mid = (lx + rx) / 2, a = 2 * x + 1, b = a + 1;
    if (i < mid)
        setter1(i, val, a, lx, mid);
    else
        setter1(i, val, b, mid, rx);
    seg[0][x] = max(seg[0][a], seg[0][b]);
}

ll get1(ll l, ll r, ll x, ll lx, ll rx){
    if (l >= rx || lx >= r)
        return 0;
    //cout << l << ' ' << r << ' ' << x << " " << lx << " " << rx << endl;
    if (l <= lx && rx <= r){
        //cout << "tah " << lx << " " << seg[0][x] << endl;
        return seg[0][x];
    }
    ll mid = (lx + rx) / 2, a = 2 * x + 1, b = a + 1;
    ll ret1 = get1(l, r, a, lx, mid);
    ll ret2 = get1(l, r, b, mid, rx);
    return max(ret1, ret2);
}

void setter2(ll i, ll val, ll x, ll lx, ll rx){
    if (rx - lx == 1){
        seg[1][x] += val;
        return;
    }
    ll mid = (lx + rx) / 2, a = 2 * x + 1, b = a + 1;
    if (i < mid)
        setter2(i, val, a, lx, mid);
    else
        setter2(i, val, b, mid, rx);
    seg[1][x] = seg[1][a] + seg[1][b];
}

ll get2(ll l, ll r, ll x, ll lx, ll rx){
    if (l >= rx || lx >= r)
        return 0;
    //cout << l << ' ' << r << ' ' << x << " " << lx << " " << rx << endl;
    if (l <= lx && rx <= r){
        //cout << "tah " << lx << " " << seg[0][x] << endl;
        return seg[1][x];
    }
    ll mid = (lx + rx) / 2, a = 2 * x + 1, b = a + 1;
    ll ret1 = get2(l, r, a, lx, mid);
    ll ret2 = get2(l, r, b, mid, rx);
    return ret1 + ret2;
}


void solve(){

cin >> n >> k;

for (int i = 1; i < n + 1; i++){
    cin >> arr[i][0] >> arr[i][1];
    comp.push_back(arr[i][0]);
    comp.push_back(arr[i][1]);
    if (arr[i][0] > arr[i][1]){
        av[i] = 1;
        swap(arr[i][0], arr[i][1]);
    }
}
for (int i = 1; i < k + 1; i++){
    cin >> brr[i];
    comp.push_back(brr[i]);
}
sort(comp.begin(), comp.end());
comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
ll cnt = 0;
while (sz <= comp.size())
    sz = sz * 2;
while (sz <= k)
    sz = sz * 2;

seg[0].resize(2 * sz);
seg[1].resize(2 * sz);
//cout << "new" << endl;
for (int i = 1; i < n + 1; i++){
    ll x = lower_bound(comp.begin(), comp.end(), arr[i][0]) - comp.begin() + 1;
    chi[x] = arr[i][0];
    arr[i][0] = x;
    x = lower_bound(comp.begin(), comp.end(), arr[i][1]) - comp.begin() + 1;
    chi[x] = arr[i][1];
    arr[i][1] = x;
    //cout << arr[i][0] << ' ' << arr[i][1] << endl;
}
for (int i = 1; i < k + 1; i++){
    ll x = lower_bound(comp.begin(), comp.end(), brr[i]) - comp.begin() + 1;
    chi[x] = brr[i];
    brr[i] = x;
    adad[brr[i]].push_back(i);
    //cout << brr[i] << endl;
    setter1(brr[i], i, 0, 0, sz);
}

ll ans = 0;

for (int i = 1; i < n + 1; i++){
    if (arr[i][0] == arr[i][1]){
        ans += chi[arr[i][0]];
        continue;
    }
    ll mx = get1(arr[i][0], arr[i][1], 0, 0, sz);
    if (mx == k){
        ans += chi[arr[i][1]];
        continue;
    }
    qu[arr[i][1]].push_back({{mx + 1, k}, i});
    //cout << i << ' ' << mx << endl;
}


//cout << "ans was " << ans << endl;


for (int i = maxn - 1; i > 0; i--){
    if (adad[i].size() == 0 && qu[i].size() == 0)
        continue;
    //cout << adad[i].size() << ' ' << qu[i].size() << endl;
    //cout << i << " started " << endl;
    for (ll x : adad[i]){
        //cout << "setting " << x << endl;
        setter2(x, 1, 0, 0, sz);
    }
    for (auto p : qu[i]){
        //cout << "qu " << p.first.first << ' ' << p.first.second << ' ' << p.second << endl;
        ll t = get2(p.first.first, p.first.second + 1, 0, 0, sz);
        //cout << "tot was " << t << endl;
        if (p.first.first == 1){
            if (t % 2 == 0){
                ans += chi[arr[p.second][av[p.second]]];
            }
            else{
                ans += chi[arr[p.second][1 - av[p.second]]];
            }
        }
        else{
            if (t % 2){
                ans += chi[arr[p.second][0]];
            }
            else{
                ans += chi[arr[p.second][1]];
            }
        }
        //cout << ans << endl;
    }
}

cout << ans << endl;


}


int main(){
//sariE;// filE;


ll test = 1;
//cin >> test;
while (test--) solve();
}

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