oj.uz

Submission #147155

# Submission time Handle Problem Language Result Execution time Memory
147155 2019-08-28T06:15:36 Z jh05013 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1323 ms 47404 KB 
#include <bits/stdc++.h>
#define dbgv(v) {for(auto x:v)cout<<x<<' ';cout<<'\n';}
#define entire(v) v.begin(),v.end()
typedef long long ll;
using namespace std;
void OJize(){
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    #ifdef jh
    freopen("input.txt", "r", stdin);
    #endif
}

// 0-indexed
template <typename T>
struct Segtree{
    T id = -2147483647;
    T combine(T a, T b){
        return max(a, b);
    }
    
    int n; vector<T> arr;
    Segtree(int sz): n{1} {
        while(n < sz) n<<=1;
        arr.resize(n*2);
    }
    void update(int i, T val){
        for(arr[i+=n] = val; i > 1; i/= 2) arr[i/2] = combine(arr[i], arr[i^1]);
    }
    T query(int l, int r){
        T resl = id, resr = id;
        for(l+= n, r+= n+1; l < r; l/= 2, r/= 2){
            if(l&1) resl = combine(resl, arr[l++]);
            if(r&1) resr = combine(resr, arr[--r]);
        }
        return combine(resl, resr);
    }
};

// 0-indexed
template <typename T>
struct Fenwick{
    int n; vector<T> arr;
    Fenwick(int n): n{n}, arr{vector<T>(n)} {}
    void construct(vector<T>& A){
        for(int i=0; i<n; i++) arr[i] = A[i];
        for(int i=0; i<n; i++) if((i|(i+1)) < n) arr[i|(i+1)]+= arr[i];
    }
    void update(int i, T val){
        while(i < n) arr[i]+= val, i |= i+1;
    }
    T getsum(int i){
        T res = 0;
        while(i >= 0) res+= arr[i], i = (i&(i+1))-1;
        return res;
    }
    T intersum(int i, int j){
        return i? (getsum(j) - getsum(i-1)) : getsum(j);
    }
};

/*
 * Treat each card individually, wlog a<b. (if a=b, trivial; if a>b, flip once.)
 * each operation x is either
 *   1. x < a: never flip
 *   2. a <= x < b: set to "flipped"
 *   3. b <= x: always flip
 * so we need to find the last occurrence of a<=x<b, then count the number of b<=x after that point.
 * last occurrence: max segtree
 * count b<=x after some point: offline sum segtree
 */

int main(){OJize();
    // Input and compression
    int n, k; cin>>n>>k;
    vector<tuple<int, int, int>> card(n); // max(a,b), a, b, index 0-i
    vector<pair<int, int>> query(k);           // x, index 1-i
    map<int, int> com;
    for(int i=0; i<n; i++){
        int a, b; cin>>a>>b;
        card[i] = make_tuple(-max(a, b), a, b);
        com[a] = com[b] = 0;
    }
    for(int i=0; i<k; i++) cin>>query[i].first, query[i].second = i+1, com[query[i].first] = 0;
    int i = 0;
    for(auto it = com.begin(); it != com.end(); it++) it->second = i++;
    sort(entire(card));
    sort(entire(query));
    
    // Segtrees
    Segtree<int> maxst(com.size()); // last index of query x, compressed, 1-i
    for(auto &xi: query) maxst.update(com[xi.first], xi.second);
    Fenwick<int> F(k+1); // current occurrence of large query at i, 1-i
    
    // Computation
    ll ans = 0;
    int CI = k-1;
    for(auto& tup: card){
        // Get compressed a and b
        int mab, ra, rb; tie(mab,ra,rb) = tup;
        if(ra == rb){ans+= ra; continue;}
        int a = com[ra], b = com[rb];
        if(a > b) swap(a, b);
        
        // Update large-number queries
        while(CI >= 0 && query[CI].first >= -mab){
            F.update(query[CI].second, 1);
            CI--;
        }
        
        // Count flips
        int last = maxst.query(a, b-1), flip = F.intersum(last, F.n-1) % 2, val;
        if(last == 0) val = flip? rb : ra;
        else val = ((ra>rb)^flip)? ra : rb;
        ans+= val;
        //cout <<ra<<' '<<rb<<" -> "<<a<<' '<<b<<" -> "<<last<<" last; "<<flip<<" flips; "<<val<<'\n';
    }
    
    cout << ans;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 632 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 4 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 4 ms 504 KB Output is correct
14 Correct 28 ms 2552 KB Output is correct
15 Correct 63 ms 4856 KB Output is correct
16 Correct 95 ms 7160 KB Output is correct
17 Correct 143 ms 9224 KB Output is correct
18 Correct 206 ms 9176 KB Output is correct
19 Correct 159 ms 9192 KB Output is correct
20 Correct 145 ms 9144 KB Output is correct
21 Correct 140 ms 9080 KB Output is correct
22 Correct 88 ms 6752 KB Output is correct
23 Correct 76 ms 5376 KB Output is correct
24 Correct 69 ms 4600 KB Output is correct
25 Correct 93 ms 7288 KB Output is correct
26 Correct 77 ms 6780 KB Output is correct
27 Correct 93 ms 7288 KB Output is correct
28 Correct 83 ms 7288 KB Output is correct
29 Correct 103 ms 8312 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 632 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 4 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 4 ms 504 KB Output is correct
14 Correct 28 ms 2552 KB Output is correct
15 Correct 63 ms 4856 KB Output is correct
16 Correct 95 ms 7160 KB Output is correct
17 Correct 143 ms 9224 KB Output is correct
18 Correct 206 ms 9176 KB Output is correct
19 Correct 159 ms 9192 KB Output is correct
20 Correct 145 ms 9144 KB Output is correct
21 Correct 140 ms 9080 KB Output is correct
22 Correct 88 ms 6752 KB Output is correct
23 Correct 76 ms 5376 KB Output is correct
24 Correct 69 ms 4600 KB Output is correct
25 Correct 93 ms 7288 KB Output is correct
26 Correct 77 ms 6780 KB Output is correct
27 Correct 93 ms 7288 KB Output is correct
28 Correct 83 ms 7288 KB Output is correct
29 Correct 103 ms 8312 KB Output is correct
30 Correct 310 ms 17416 KB Output is correct
31 Correct 553 ms 24516 KB Output is correct
32 Correct 796 ms 30776 KB Output is correct
33 Correct 1213 ms 47308 KB Output is correct
34 Correct 260 ms 16120 KB Output is correct
35 Correct 1182 ms 47352 KB Output is correct
36 Correct 1205 ms 47404 KB Output is correct
37 Correct 1323 ms 47352 KB Output is correct
38 Correct 1161 ms 47352 KB Output is correct
39 Correct 1274 ms 47320 KB Output is correct
40 Correct 1062 ms 47068 KB Output is correct
41 Correct 1164 ms 47192 KB Output is correct
42 Correct 1177 ms 47352 KB Output is correct
43 Correct 681 ms 46712 KB Output is correct
44 Correct 685 ms 46712 KB Output is correct
45 Correct 695 ms 46584 KB Output is correct
46 Correct 545 ms 27256 KB Output is correct
47 Correct 470 ms 20292 KB Output is correct
48 Correct 696 ms 33952 KB Output is correct
49 Correct 631 ms 33888 KB Output is correct