Submission #1289773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289773		Mahog	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	1167 ms	101412 KiB

fortune_telling2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
struct segtree {
    vector<int> a, b;
    int n = 0;
    int o = 0;
    
    int merge(int x, int y) {
    	return max(x, y);
    }
    
    void start(int x) {
        n = x;
        for (int i = 0; i <= n; i++) a.push_back(o);
        for (int i = 0; i <= 4 * n; i++) b.push_back(o);
        n = 0;
    }
    
    void insertVal(int x) {
        n++;
        a[n] = x;
    }
        
    void build(int d, int l, int r) {
        if (l == r) b[d] = a[l];
        else {
            int mid = (l + r) / 2;
            build(d * 2, l, mid);
            build(d * 2 + 1, mid + 1, r);
            b[d] = merge(b[d * 2], b[d * 2 + 1]);
        }
    }
    
    void update(int d, int l, int r, int v, int x) {
        if (l == r) {
            b[d] = merge(b[d], x);
        } else {
            int mid = (l + r) / 2;
            if (v <= mid) update(d * 2, l, mid, v, x);
            else update(d * 2 + 1, mid + 1, r, v, x);
            b[d] = merge(b[d * 2], b[d * 2 + 1]);
        }
    }
    	
    int query(int d, int l, int r, int u, int v) {
        if (u > v) return o;
        else if (l == u && r == v) return b[d];
        else {
            int mid = (l + r) / 2;
            return merge(query(d * 2, l, mid, u, min(mid, v)), query(d * 2 + 1, mid + 1, r, max(mid + 1, u), v));
        }
    }
};

struct segtree2 {
    vector<int> a, b;
    int n = 0;
    int o = 0;
    
    int merge(int x, int y) {
    	return x + y;
    }
    
    void start(int x) {
        n = x;
        for (int i = 0; i <= n; i++) a.push_back(o);
        for (int i = 0; i <= 4 * n; i++) b.push_back(o);
        n = 0;
    }
    
    void insertVal(int x) {
        n++;
        a[n] = x;
    }
        
    void build(int d, int l, int r) {
        if (l == r) b[d] = a[l];
        else {
            int mid = (l + r) / 2;
            build(d * 2, l, mid);
            build(d * 2 + 1, mid + 1, r);
            b[d] = merge(b[d * 2], b[d * 2 + 1]);
        }
    }
    
    void update(int d, int l, int r, int v, int x) {
        if (l == r) {
            b[d] = merge(b[d], x);
        } else {
            int mid = (l + r) / 2;
            if (v <= mid) update(d * 2, l, mid, v, x);
            else update(d * 2 + 1, mid + 1, r, v, x);
            b[d] = merge(b[d * 2], b[d * 2 + 1]);
        }
    }
    	
    int query(int d, int l, int r, int u, int v) {
        if (u > v) return o;
        else if (l == u && r == v) return b[d];
        else {
            int mid = (l + r) / 2;
            return merge(query(d * 2, l, mid, u, min(mid, v)), query(d * 2 + 1, mid + 1, r, max(mid + 1, u), v));
        }
    }
};

struct foot {
    int x, idx;
};

const int MAX = 2e5 + 2;
pair<int, int> a[MAX];
int b[MAX], d[MAX], n, k;
foot c[MAX];

bool cmp(foot x, foot y) {
    return x.x > y.x;
}

void solve() {
    cin >> n >> k;
    map<int, int> mp, mp1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
        if (a[i].first > a[i].second) {
            swap(a[i].first, a[i].second);
            d[i] = 1;
        }
        mp[a[i].first]++;
        mp[a[i].second]++;
    }
    for (int i = 1; i <= k; i++) {
        cin >> b[i];
        mp[b[i]]++;
    }
    int cnt = 0;
    for (auto i : mp) {
        mp[i.first] = ++cnt;
        mp1[cnt] = i.first;
    }
    for (int i = 1; i <= n; i++) {
        a[i].first = mp[a[i].first];
        a[i].second = mp[a[i].second];
    }
    for (int i = 1; i <= k; i++) b[i] = mp[b[i]];
    int m = mp.size();
    segtree st;
    st.start(m);
    for (int i = 1; i <= m; i++) st.insertVal(0);
    st.build(1, 1, m);
    for (int i = 1; i <= k; i++) st.update(1, 1, m, b[i], i);
    for (int i = 1; i <= n; i++) {
        int temp = st.query(1, 1, m, a[i].first, a[i].second - 1);
        c[i] = {temp, i};
        //cout << temp << " ";
    }
    //cout << "\n";
    sort(c + 1, c + n + 1, cmp);
    segtree2 st2;
    st2.start(m);
    for (int i = 1; i <= m; i++) st2.insertVal(0);
    st2.build(1, 1, m);
    int j = k;
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        while (j > c[i].x) {
            st2.update(1, 1, m, b[j], 1);
            j--;
        }
        int temp = st2.query(1, 1, m, a[c[i].idx].second, m);
        int temp1;
        if (c[i].x == 0) {
            if ((d[c[i].idx] + temp) % 2 == 0) temp1 = a[c[i].idx].first;
            else temp1 = a[c[i].idx].second;
        } else {
            if (temp % 2 == 0) temp1 = a[c[i].idx].second;
            else temp1 = a[c[i].idx].first;
        }
        res += mp1[temp1];
        //cout << c[i].idx << " " << mp1[temp1] << "\n";
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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