Submission #131908

#	Time	Username	Problem	Language	Result	Execution time	Memory
131908		DifferentHeaven	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	1547 ms	79596 KiB

fortune_telling2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
#define _ << ", " << 

using namespace __gnu_pbds;
using namespace std;

inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}

const int N = 1e6 + 7;
const int oo = 1e9 + 7;

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

int n, k, g;
ii card[N];
int t[N], rev[5 * N];
vector <int> v;
vector <ii> vt;
map <int, int> mp;
long long res;

struct segTree{
    int tree[4 * N], l[4 * N], h[4 * N];
    int leaf[N];

    void Build(int x, int low, int high){
        l[x] = low; h[x] = high;
        if (low == high){
            leaf[low] = x;
            tree[x] = -oo;
        }
        else{
            int mid = low + high >> 1;
            Build(2 * x, low, mid);
            Build(2 * x + 1, mid + 1, high);
            tree[x] = max(tree[2 * x], tree[2 * x + 1]);
        }
    }

    void Update(int x, int val){
        x = leaf[x];
        tree[x] = val;
        while (1){
            x >>= 1;
            if (x == 0) break;
            tree[x] = max(tree[2 * x], tree[2 * x + 1]);
        }
    }

    int Query(int x, int i, int j){
        if (l[x] > j || h[x] < i) return -oo;
        if (l[x] >= i && h[x] <= j) return tree[x];
        int L = Query(2 * x, i, j);
        int R = Query(2 * x + 1, i, j);
        return max(L, R);
    }
}IT;

inline void compressData(){
    sort(v.begin(), v.end());

    mp[v[0]] = ++g;
    rev[g] = v[0];
    for (int i = 1; i < v.size(); i++)
        if (v[i] != v[i - 1]){
            mp[v[i]] = ++g;
            rev[g] = v[i];
        }
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	// freopen("test.inp", "r", stdin);
	// freopen("test.out", "w", stdout);   

    read(n); read(k);
    for (int i = 1; i <= n; i++){
        read(card[i].x); read(card[i].y);
        v.push_back(card[i].x);
        v.push_back(card[i].y);
    }

    for (int i = 1; i <= k; i++){
        read(t[i]);
        v.push_back(t[i]);
    }

    compressData();

    IT.Build(1, 1, g);

    for (int i = 1; i <= k; i++){
        t[i] = mp[t[i]];
        vt.push_back(ii(t[i], i));
        IT.Update(t[i], i);
    }

    sort(vt.begin(), vt.end());

    for (int i = 1; i <= n; i++){
        card[i].x = mp[card[i].x];
        card[i].y = mp[card[i].y];
    }

    sort(card + 1, card + n + 1, [] (ii a, ii b) {
        return max(a.x, a.y) > max(b.x, b.y);
    });

    ordered_set certain; // ordered_set

    for (int i = 1; i <= n; i++){
        int mn = min(card[i].x, card[i].y);
        int mx = max(card[i].x, card[i].y);

        /* 3 types of flip
        - T < mn: nothing done
        - mn <= T < mx: will flip the mx value to upper face
        - mx <= T: will flip the card no matter what face is up
        KEY OBSERVATION: 
        - If the latest 2nd-type operation happens, it will result in card with mx value on top
        - In contrast, mx value is already on top
        ====> mx value is always on top if there is a 2nd-type operation.
        */ 

        while (vt.size() && vt.back().x >= mx){
            certain.insert(vt.back().y);
            vt.pop_back();
        }

        int lastBetween = IT.Query(1, mn, mx - 1);
        int remainingFlip = (certain.size() - certain.order_of_key(lastBetween)) % 2;

        // db(lastBetween _ remainingFlip);

        int id;

        if (lastBetween == -oo)
            id = (remainingFlip ? card[i].y : card[i].x); 
        else 
            id = (remainingFlip ? mn : mx);

        res += rev[id];
        // db(rev[id]);
    }

    writeln(res);
}

Compilation message (stderr)

fortune_telling2.cpp: In member function 'void segTree::Build(int, int, int)':
fortune_telling2.cpp:43:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid = low + high >> 1;
                       ~~~~^~~~~~
fortune_telling2.cpp: In function 'void compressData()':
fortune_telling2.cpp:74:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < v.size(); i++)
                     ~~^~~~~~~~~~

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