oj.uz

Submission #131904

# Submission time Handle Problem Language Result Execution time Memory
131904 2019-07-18T03:04:08 Z DifferentHeaven Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 228 ms 13300 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);
        int remainingFlip = (certain.size() - certain.order_of_key(lastBetween)) % 2;

        int id;

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

        res += 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 796 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 600 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 764 KB Output is correct

Subtask #2
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 796 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 600 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 764 KB Output is correct
14 Correct 37 ms 3576 KB Output is correct
15 Correct 82 ms 6900 KB Output is correct
16 Correct 155 ms 10820 KB Output is correct
17 Correct 198 ms 13296 KB Output is correct
18 Correct 200 ms 13292 KB Output is correct
19 Correct 188 ms 12784 KB Output is correct
20 Correct 192 ms 13300 KB Output is correct
21 Correct 228 ms 12000 KB Output is correct
22 Correct 112 ms 10224 KB Output is correct
23 Incorrect 121 ms 7908 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
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 796 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 600 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 764 KB Output is correct
14 Correct 37 ms 3576 KB Output is correct
15 Correct 82 ms 6900 KB Output is correct
16 Correct 155 ms 10820 KB Output is correct
17 Correct 198 ms 13296 KB Output is correct
18 Correct 200 ms 13292 KB Output is correct
19 Correct 188 ms 12784 KB Output is correct
20 Correct 192 ms 13300 KB Output is correct
21 Correct 228 ms 12000 KB Output is correct
22 Correct 112 ms 10224 KB Output is correct
23 Incorrect 121 ms 7908 KB Output isn't correct
24 Halted 0 ms 0 KB -