oj.uz

Submission #131908

# Submission time Handle Problem Language Result Execution time Memory
131908 2019-07-18T03:29:37 Z DifferentHeaven Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 1547 ms 79596 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 4 ms 760 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 4 ms 632 KB Output is correct
13 Correct 4 ms 636 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 4 ms 760 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 4 ms 632 KB Output is correct
13 Correct 4 ms 636 KB Output is correct
14 Correct 37 ms 3544 KB Output is correct
15 Correct 85 ms 6868 KB Output is correct
16 Correct 141 ms 10864 KB Output is correct
17 Correct 194 ms 13172 KB Output is correct
18 Correct 199 ms 13256 KB Output is correct
19 Correct 193 ms 12716 KB Output is correct
20 Correct 232 ms 13152 KB Output is correct
21 Correct 198 ms 11744 KB Output is correct
22 Correct 112 ms 10072 KB Output is correct
23 Correct 101 ms 7804 KB Output is correct
24 Correct 98 ms 8176 KB Output is correct
25 Correct 109 ms 11124 KB Output is correct
26 Correct 118 ms 11632 KB Output is correct
27 Correct 138 ms 12276 KB Output is correct
28 Correct 133 ms 12144 KB Output is correct
29 Correct 155 ms 13212 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 4 ms 760 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 4 ms 632 KB Output is correct
13 Correct 4 ms 636 KB Output is correct
14 Correct 37 ms 3544 KB Output is correct
15 Correct 85 ms 6868 KB Output is correct
16 Correct 141 ms 10864 KB Output is correct
17 Correct 194 ms 13172 KB Output is correct
18 Correct 199 ms 13256 KB Output is correct
19 Correct 193 ms 12716 KB Output is correct
20 Correct 232 ms 13152 KB Output is correct
21 Correct 198 ms 11744 KB Output is correct
22 Correct 112 ms 10072 KB Output is correct
23 Correct 101 ms 7804 KB Output is correct
24 Correct 98 ms 8176 KB Output is correct
25 Correct 109 ms 11124 KB Output is correct
26 Correct 118 ms 11632 KB Output is correct
27 Correct 138 ms 12276 KB Output is correct
28 Correct 133 ms 12144 KB Output is correct
29 Correct 155 ms 13212 KB Output is correct
30 Correct 527 ms 33296 KB Output is correct
31 Correct 721 ms 45476 KB Output is correct
32 Correct 957 ms 52676 KB Output is correct
33 Correct 1517 ms 79332 KB Output is correct
34 Correct 356 ms 24428 KB Output is correct
35 Correct 1547 ms 79596 KB Output is correct
36 Correct 1446 ms 79356 KB Output is correct
37 Correct 1507 ms 79536 KB Output is correct
38 Correct 1354 ms 76584 KB Output is correct
39 Correct 1433 ms 79456 KB Output is correct
40 Correct 1167 ms 71920 KB Output is correct
41 Correct 1348 ms 78600 KB Output is correct
42 Correct 1423 ms 79180 KB Output is correct
43 Correct 782 ms 71392 KB Output is correct
44 Correct 800 ms 71544 KB Output is correct
45 Correct 775 ms 71456 KB Output is correct
46 Correct 775 ms 45708 KB Output is correct
47 Correct 732 ms 37004 KB Output is correct
48 Correct 964 ms 56168 KB Output is correct
49 Correct 915 ms 56148 KB Output is correct