Submission #791362

#	Time	Username	Problem	Language	Result	Execution time	Memory
791362		Cookie	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	4 / 100	72 ms	18820 KiB

fortune_telling2

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 6e5, base = 74;
const ll p = 31, mod = 1e9 + 7;
int n, k;
int st[4 * mxn + 1], bit[mxn + 1];
void upd(int nd, int l, int r, int id, int v){
    if(id < l || id > r)return;
    if(l == r){
        st[nd] = max(st[nd], v);
        return;
    }
    int mid = (l + r) >> 1;
    upd(nd << 1, l, mid, id, v); upd(nd << 1 | 1, mid + 1, r, id, v);
    st[nd] = max(st[nd << 1], st[nd << 1 | 1]);
}
int get(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return(0);
    if(ql <= l && qr >= r)return(st[nd]);
    int mid = (l + r) >> 1;
    return(max(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
}
vt<int>comp;
void updbit(int p, int v){
    while(p <= sz(comp)){
        bit[p] += v; p += p & (-p);
    }
}
int getbit(int p){
    int ans = 0;
    while(p){
        ans += bit[p]; p -= p & (-p);
    }
    return(ans);
}
int find(int x){
    return(lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1);
}
vt<int>q[mxn + 1];
ll a[mxn + 1], b[mxn + 1], c[mxn + 1];
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i]; comp.pb(a[i]); comp.pb(b[i]);
    }
    for(int i = 1; i <= k; i++){
        cin >> c[i]; comp.pb(c[i]);
    }
    sort(comp.begin(), comp.end());
    for(int i = 1; i <= k; i++){
        upd(1, 1, sz(comp), find(c[i]), i);
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        int mn = find(min(a[i], b[i])), mx = find(max(a[i], b[i]));
        if(mn == mx){
            ans += comp[mn - 1];
            continue;
        }
        int mxid = get(1, 1, sz(comp), mn, mx - 1);
        //cout << i << " " << mxid << "\n";
        q[mxid].pb(i);
    }
    for(int i = k; i >= 1; i--){
        for(auto j: q[i]){
            int mx = find(max(a[j], b[j]));
            ll turn = getbit(sz(comp)) - getbit(mx - 1);
            //cout << i << " " << j << " " << turn << "\n";
            if(turn & 1){
                ans += min(a[j], b[j]);
            }else{
                ans += max(a[j], b[j]);
            }
        }
        updbit(find(c[i]), 1);
    }
    for(auto i: q[0]){
        int mx = find(max(a[i], b[i]));
        int turn = getbit(sz(comp)) - getbit(mx);
        if(turn % 2 == 0)ans += a[i];
        else ans += b[i];
    }
    cout << ans;
    return(0);
}

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