oj.uz

Submission #131708

# Submission time Handle Problem Language Result Execution time Memory
131708 2019-07-17T13:12:50 Z DifferentHeaven Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 202 ms 13360 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 3 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 760 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 5 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 504 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 760 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 3 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 760 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 5 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 504 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 760 KB Output is correct
14 Correct 38 ms 3576 KB Output is correct
15 Correct 95 ms 6788 KB Output is correct
16 Correct 140 ms 10712 KB Output is correct
17 Correct 194 ms 13360 KB Output is correct
18 Correct 195 ms 13116 KB Output is correct
19 Correct 202 ms 12756 KB Output is correct
20 Correct 184 ms 13172 KB Output is correct
21 Correct 170 ms 11808 KB Output is correct
22 Correct 114 ms 10096 KB Output is correct
23 Incorrect 99 ms 7788 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 3 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 760 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 5 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 504 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 760 KB Output is correct
14 Correct 38 ms 3576 KB Output is correct
15 Correct 95 ms 6788 KB Output is correct
16 Correct 140 ms 10712 KB Output is correct
17 Correct 194 ms 13360 KB Output is correct
18 Correct 195 ms 13116 KB Output is correct
19 Correct 202 ms 12756 KB Output is correct
20 Correct 184 ms 13172 KB Output is correct
21 Correct 170 ms 11808 KB Output is correct
22 Correct 114 ms 10096 KB Output is correct
23 Incorrect 99 ms 7788 KB Output isn't correct
24 Halted 0 ms 0 KB -