Submission #900422

#	Time	Username	Problem	Language	Result	Execution time	Memory
900422		Turkhuu	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	264 ms	27704 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T>
struct segtree {
    int n;
    T e;
    T (*f)(T, T);
    vector<T> s;
    segtree(int n, T (*f)(T, T), T e):
    n(n), e(e), f(f), s(2 * n, e) {
    }
    segtree(const vector<T> &a, T (*f)(T, T), T e):
    segtree(a.size(), f, e) {
        for (int i = 2 * n - 1; i; i--) {
            s[i] = i < n ? f(s[i * 2], s[i * 2 + 1]) : a[i - n];
        }
    }
    void set(int i, const T &v) {
        for (i += n, s[i] = v; i /= 2;) {
            s[i] = f(s[i * 2], s[i * 2 + 1]);
        }
    }
    T qry(int l, int r) {
        T u(e), v(e);
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l & 1) u = f(u, s[l++]);
            if (r & 1) v = f(s[--r], v);
        }
        return f(u, v);
    }
};
int f(int x, int y) {
    return max(x, y);
}
int g(int x, int y) {
    return x ^ y;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    cin >> N >> K;
    vector<int> A(N), B(N), T(K);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
    for (int i = 0; i < K; i++) cin >> T[i];
    vector<int> v;
    v.insert(v.end(), A.begin(), A.end());
    v.insert(v.end(), B.begin(), B.end());
    v.insert(v.end(), T.begin(), T.end());
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (auto &i : A) i = lower_bound(v.begin(), v.end(), i) - v.begin();
    for (auto &i : B) i = lower_bound(v.begin(), v.end(), i) - v.begin();
    for (auto &i : T) i = lower_bound(v.begin(), v.end(), i) - v.begin();
    int M = v.size();
    segtree<int> s1(M, f, -1);
    for (int i = 0; i < K; i++) s1.set(T[i], i);
    vector<int> a(N);
    vector<vector<int>> b(K);
    for (int i = 0; i < N; i++) {
        a[i] = s1.qry(min(A[i], B[i]), max(A[i], B[i]));
        if (a[i] != -1) b[a[i]].push_back(i);
    }
    ll ans = 0;
    segtree<int> s2(M, g, 0);
    for (int i = K - 1; i >= 0; i--) {
        for (int j : b[i]) {
            ans += s2.qry(max(A[j], B[j]), M) ? v[min(A[j], B[j])] : v[max(A[j], B[j])];
        }
        s2.set(T[i], s2.qry(T[i], T[i] + 1) ^ 1);
    }
    for (int i = 0; i < N; i++) {
        if (a[i] == -1) {
            ans += s2.qry(A[i], M) ? v[B[i]] : v[A[i]];
        }
    }
    cout << ans;
    return 6/22;
}

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