Submission #908754

#	Time	Username	Problem	Language	Result	Execution time	Memory
908754		typ_ik	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	324 ms	60616 KiB

fortune_telling2

#include <bits/stdc++.h>

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) <<  " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;   

const int N = 2e5 + 128;
int n, k;
int a[N], b[N], c[N];
vector <int> t[4 * N];

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v].push_back(c[tl]);
        return;
    }
    int tm = (tl + tr) >> 1;
    build(v << 1, tl, tm);
    build(v << 1 | 1, tm + 1, tr);
    merge(all(t[v << 1]), all(t[v << 1 | 1]), back_inserter(t[v]));
}

int get(int l, int r, int x, int v, int tl, int tr) {
    if (tl > r || tr < l)
        return 0;
    if (l <= tl && tr <= r)
        return (int)t[v].size() - (int)(lower_bound(all(t[v]), x) - t[v].begin());
    int tm = (tl + tr) >> 1;
    return get(l, r, x, v << 1, tl, tm) +
            get(l, r, x, v << 1 | 1, tm + 1, tr);
} 

const int INF = 2e9 + 128;
int mx[4 * N];

void update(int pos, int val, int v, int tl, int tr) {
    if (tl > pos || tr < pos)
        return;
    if (tl == tr) {
        mx[v] = val;
        return;
    }
    int tm = (tl + tr) >> 1;
    update(pos, val, v << 1, tl, tm);
    update(pos, val, v << 1 | 1, tm + 1, tr);
    mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
}

int rightmost(int l, int r, int x, int v, int tl, int tr) {
    if (tl > r || tr < l || mx[v] < x)
        return -1; 
    if (tl == tr)
        return tl;
    int tm = (tl + tr) >> 1;
    if (l <= tl && tr <= r) { 
        if (mx[v << 1 | 1] >= x)
            return rightmost(l, r, x, v << 1 | 1, tm + 1, tr);
        else if (mx[v << 1] >= x)
            return rightmost(l, r, x, v << 1, tl, tm); 
        return -1;
    } 
    return max(rightmost(l, r, x, v << 1, tl, tm), rightmost(l, r, x, v << 1 | 1, tm + 1, tr));
} 

void solve() {  
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i] >> b[i];
    for (int i = 0; i < k; i++)
        cin >> c[i]; 
    
    build(1, 0, k - 1);

    vector <int> order(n);  
    iota(all(order), 0);
    sort(all(order), [&](const int& x, const int& y) -> bool {
        return max(a[x], b[x]) < max(a[y], b[y]); 
    });

    vector < pair<int, int> > to_add;
    for (int i = 0; i < k; i++)
        to_add.push_back(make_pair(c[i], i));
    sort(all(to_add));
    
    ll ans = 0;

    vector <int> pref(k);
    for (int i = 0; i < k; i++)
        pref[i] = max((i ? pref[i - 1] : 0), c[i]); 
 
    for (int i = 0; i < k; i++)
        update(i, -INF, 1, 0, k - 1); 
    
    int pt = 0;

    for (auto& i : order) {  
        int x = -1;  
        if (a[i] > b[i]) { 
            x = (int)(lower_bound(all(pref), a[i]) - pref.begin());  
            if (x == k) { 
                ans += a[i];
                continue;
            }
            swap(a[i], b[i]);
        }

        assert(a[i] <= b[i]);
        while (pt < k && to_add[pt].first < b[i])
            update(to_add[pt].second, to_add[pt].first, 1, 0, k - 1), pt++; 

        int pos = rightmost(x + 1, k - 1, a[i], 1, 0, k - 1);  

        bool was = (pos < 0);
        if (was)
            pos = x; 

        int lefts = get(pos + 1, k - 1, b[i], 1, 0, k - 1);   
        
        ans += ((lefts % 2 == was) ? b[i] : a[i]); 
    } 

    cout << ans << '\n';
}

main() {
    boost;
    solve();
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp:129:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  129 | main() {
      | ^~~~

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