Submission #1130536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130536		ByeWorld	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	0 / 100	11 ms	14912 KiB

fortune_telling2

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 6e5+10;
const int MAXA = 1e6;
const int INF = 1e18+10;
const int MOD = 1e9+7;
const int LOG = 20;
const ld EPS = 1e-12;

int n, k, a[MAXN], b[MAXN], q[MAXN];
int st[MAXN][LOG+5], val[MAXN];
vector<int> cc;
vector <pii> vec[MAXN];

int QUE(int l, int r){
    if(l>r) return 0;
    int len = log2(r-l+1);
    return max(st[l][len], st[r-(1<<len)+1][len]);
}
struct seg {
    int st[2*MAXN];
    int que(int x){
        int te = 0;
        for(; x>=1; x-=(x&(-x))) te += st[x];
        return te;
    }
    void upd(int x, int p){
        for(; x<=2*MAXN-20; x+=(x&(-x))) st[x] += p;
    }
} A;
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> k;
    cc.pb(-1);
    for(int i=1; i<=n; i++){
        cin >> a[i]>>b[i];cc.pb(a[i]);cc.pb(b[i]);
    }
    for(int i=1; i<=k; i++){
        cin >> q[i]; cc.pb(q[i]);
    }
    sort(cc.begin(), cc.end());
    cc.resize(unique(cc.begin(), cc.end()) - cc.begin());

    for(int i=1; i<=k; i++){
        int id = lower_bound(cc.begin(), cc.end(), q[i]) - cc.begin();
        st[id][0] = i;
    }
    for(int j=1; j<LOG; j++)
        for(int i=1; i+(1<<j)-1<=cc.size(); i++)
            st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
    
    int ans = 0;
    for(int i=1; i<=n; i++){
        int le = lower_bound(cc.begin(), cc.end(), min(a[i],b[i])) - cc.begin();
        int ri = lower_bound(cc.begin(), cc.end(), max(a[i],b[i])) - cc.begin() - 1;
        int las = QUE(le, ri);
        // cout <<i << ' '<< las <<"las\n";
        if(las == 0) vec[0].pb({max(le,ri), i});
        else vec[las+1].pb({max(le,ri), i});
    }
    for(int i=k; i>=1; i--){
        int id = lower_bound(cc.begin(), cc.end(), q[i]) - cc.begin();
        A.upd(id, 1);
        for(auto [val, idx] : vec[i]){
            int tot = k-i+1 - A.que(val);
            // cout << idx << " idx\n";
            if(tot%2 == 0){
                ans += max(a[idx], b[idx]);
                // cout << max(a[idx], b[idx]) << "max\n";
            } else {
                ans += min(a[idx],b[idx]);
                // cout << min(a[idx], b[idx]) << "min\n";
            }
        }
    }
    for(auto [val, idx] : vec[0]){
        int tot = k - A.que(val);
        // cout << idx << " idx\n";
        if(tot%2 == 0){
            ans += a[idx];
            // cout << a[idx] << "a\n";
        } else {
            ans += b[idx];
            // cout << b[idx] << "b\n";
        }
    }
    cout << ans << '\n';
} 

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