oj.uz

Submission #131702

# Submission time Handle Problem Language Result Execution time Memory
131702 2019-07-17T13:11:17 Z DifferentHeaven Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 213 ms 14452 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 = 2e5 + 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 4 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 5 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 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 4 ms 760 KB Output is correct
12 Correct 4 ms 632 KB Output is correct
13 Correct 4 ms 760 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 5 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 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 4 ms 760 KB Output is correct
12 Correct 4 ms 632 KB Output is correct
13 Correct 4 ms 760 KB Output is correct
14 Correct 40 ms 3956 KB Output is correct
15 Correct 85 ms 7416 KB Output is correct
16 Correct 145 ms 11608 KB Output is correct
17 Correct 200 ms 14452 KB Output is correct
18 Correct 213 ms 14320 KB Output is correct
19 Correct 187 ms 13764 KB Output is correct
20 Correct 193 ms 14316 KB Output is correct
21 Correct 191 ms 12916 KB Output is correct
22 Correct 126 ms 10736 KB Output is correct
23 Incorrect 104 ms 8436 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 5 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 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 4 ms 760 KB Output is correct
12 Correct 4 ms 632 KB Output is correct
13 Correct 4 ms 760 KB Output is correct
14 Correct 40 ms 3956 KB Output is correct
15 Correct 85 ms 7416 KB Output is correct
16 Correct 145 ms 11608 KB Output is correct
17 Correct 200 ms 14452 KB Output is correct
18 Correct 213 ms 14320 KB Output is correct
19 Correct 187 ms 13764 KB Output is correct
20 Correct 193 ms 14316 KB Output is correct
21 Correct 191 ms 12916 KB Output is correct
22 Correct 126 ms 10736 KB Output is correct
23 Incorrect 104 ms 8436 KB Output isn't correct
24 Halted 0 ms 0 KB -