제출 #133960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133960		egorlifar	운세 보기 2 (JOI14_fortune_telling2)	C++17	100 / 100	624 ms	31732 KiB

fortune_telling2

/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 */
#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>


using namespace std;
using namespace __gnu_pbds;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left224
#define right right224
#define next next224
#define rank rank224
#define prev prev224
#define y1 y1224
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
const string FILENAME = "input";
const int MAXN = 200228;
const int INF = 1e9;


typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


int n, k;
int a[MAXN], b[MAXN], t[MAXN];
pair<int, int> p[MAXN];


struct rmq
{
    vector<int> d;
    int ss = 1;
    void init(int n) {
        while (ss < n) {
            ss <<= 1;
        }
        d.resize(2 * ss);
        for (int i = 0; i < 2 * ss; i++) {
            d[i] = -INF;
        }
    }
    void upd(int i, int val) {
        i += ss - 1;
        d[i] = val;
        while (i >> 1 > 0) {
            i >>= 1;
            d[i] = max(d[i * 2], d[i * 2 + 1]);
        }
    }
    int get(int l, int r) {
        l += ss - 1;
        r += ss - 1;
        int res = -INF;
        while (l <= r) {
            if (l & 1) {
                chkmax(res, d[l]);
                l++;
            }
            if (!(r & 1)) {
                chkmax(res, d[r]);
                r--;
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};


rmq kek;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME);
    cin >> n >> k;
    vector<int> vx;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        vx.pb(a[i]);
        vx.pb(b[i]);
    }
    for (int i = 1; i <= k; i++) {
        cin >> t[i];
        vx.pb(t[i]);
    }
    sort(all(vx));
    vx.resize(distance(vx.begin(), unique(all(vx))));
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(all(vx), a[i]) - vx.begin() + 1;
        b[i] = lower_bound(all(vx), b[i]) - vx.begin() + 1;
    }
    kek.init(sz(vx));
    vector<pair<int, int> > st;
    for (int i = 1; i <= k; i++) {
        int uk = lower_bound(all(vx), t[i]) - vx.begin() + 1;
        kek.upd(uk, i);
        st.pb({uk, i});
    }
    sort(all(st));
    for (int i = 1; i <= n; i++) {
        p[i] = {a[i], b[i]};
    }
    sort(p + 1, p + n + 1, [](pair<int, int> a, pair<int, int> b){return max(a.first, a.second) > max(b.first, b.second);});
    long long ans = 0;
    ordered_set certain;
    for (int i = 1; i <= n; i++) {
        int mn = min(p[i].first, p[i].second);
        int mx = max(p[i].first, p[i].second);
        while (sz(st) && st.back().first >= mx){
            certain.insert(st.back().second);
            st.pop_back();
        }
        int lastBetween = kek.get(mn, mx - 1);
        int remainingFlip = (sz(certain) - certain.order_of_key(lastBetween)) % 2;
        int id;
        if (lastBetween == -INF) {
            id = (remainingFlip ? p[i].second: p[i].first);
        }  else {
            id = (remainingFlip ? mn: mx);
        }
       // cout << id << endl;
        ans += vx[id - 1];
    }
    cout << ans << endl;
    return 0;
}

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