oj.uz

Submission #52182

# Submission time Handle Problem Language Result Execution time Memory
52182 2018-06-24T14:17:43 Z `مرحبا بالعالم`(#1336) Fortune Telling 2 (JOI14_fortune_telling2) C++11
100 / 100
 1525 ms 42204 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 2 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 4 ms 684 KB Output is correct
4 Correct 4 ms 744 KB Output is correct
5 Correct 4 ms 744 KB Output is correct
6 Correct 4 ms 800 KB Output is correct
7 Correct 4 ms 800 KB Output is correct
8 Correct 4 ms 800 KB Output is correct
9 Correct 4 ms 800 KB Output is correct
10 Correct 3 ms 800 KB Output is correct
11 Correct 3 ms 800 KB Output is correct
12 Correct 3 ms 800 KB Output is correct
13 Correct 4 ms 800 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 4 ms 684 KB Output is correct
4 Correct 4 ms 744 KB Output is correct
5 Correct 4 ms 744 KB Output is correct
6 Correct 4 ms 800 KB Output is correct
7 Correct 4 ms 800 KB Output is correct
8 Correct 4 ms 800 KB Output is correct
9 Correct 4 ms 800 KB Output is correct
10 Correct 3 ms 800 KB Output is correct
11 Correct 3 ms 800 KB Output is correct
12 Correct 3 ms 800 KB Output is correct
13 Correct 4 ms 800 KB Output is correct
14 Correct 28 ms 2608 KB Output is correct
15 Correct 63 ms 4412 KB Output is correct
16 Correct 123 ms 6688 KB Output is correct
17 Correct 163 ms 8504 KB Output is correct
18 Correct 166 ms 8504 KB Output is correct
19 Correct 154 ms 8508 KB Output is correct
20 Correct 156 ms 8508 KB Output is correct
21 Correct 146 ms 8508 KB Output is correct
22 Correct 98 ms 8508 KB Output is correct
23 Correct 76 ms 8508 KB Output is correct
24 Correct 70 ms 8508 KB Output is correct
25 Correct 105 ms 8508 KB Output is correct
26 Correct 96 ms 8508 KB Output is correct
27 Correct 96 ms 8508 KB Output is correct
28 Correct 95 ms 8508 KB Output is correct
29 Correct 114 ms 8508 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 4 ms 684 KB Output is correct
4 Correct 4 ms 744 KB Output is correct
5 Correct 4 ms 744 KB Output is correct
6 Correct 4 ms 800 KB Output is correct
7 Correct 4 ms 800 KB Output is correct
8 Correct 4 ms 800 KB Output is correct
9 Correct 4 ms 800 KB Output is correct
10 Correct 3 ms 800 KB Output is correct
11 Correct 3 ms 800 KB Output is correct
12 Correct 3 ms 800 KB Output is correct
13 Correct 4 ms 800 KB Output is correct
14 Correct 28 ms 2608 KB Output is correct
15 Correct 63 ms 4412 KB Output is correct
16 Correct 123 ms 6688 KB Output is correct
17 Correct 163 ms 8504 KB Output is correct
18 Correct 166 ms 8504 KB Output is correct
19 Correct 154 ms 8508 KB Output is correct
20 Correct 156 ms 8508 KB Output is correct
21 Correct 146 ms 8508 KB Output is correct
22 Correct 98 ms 8508 KB Output is correct
23 Correct 76 ms 8508 KB Output is correct
24 Correct 70 ms 8508 KB Output is correct
25 Correct 105 ms 8508 KB Output is correct
26 Correct 96 ms 8508 KB Output is correct
27 Correct 96 ms 8508 KB Output is correct
28 Correct 95 ms 8508 KB Output is correct
29 Correct 114 ms 8508 KB Output is correct
30 Correct 358 ms 15640 KB Output is correct
31 Correct 533 ms 22088 KB Output is correct
32 Correct 861 ms 27464 KB Output is correct
33 Correct 1525 ms 42036 KB Output is correct
34 Correct 379 ms 42036 KB Output is correct
35 Correct 1359 ms 42036 KB Output is correct
36 Correct 1426 ms 42036 KB Output is correct
37 Correct 1366 ms 42204 KB Output is correct
38 Correct 1393 ms 42204 KB Output is correct
39 Correct 1500 ms 42204 KB Output is correct
40 Correct 1378 ms 42204 KB Output is correct
41 Correct 1475 ms 42204 KB Output is correct
42 Correct 1454 ms 42204 KB Output is correct
43 Correct 757 ms 42204 KB Output is correct
44 Correct 739 ms 42204 KB Output is correct
45 Correct 725 ms 42204 KB Output is correct
46 Correct 600 ms 42204 KB Output is correct
47 Correct 502 ms 42204 KB Output is correct
48 Correct 759 ms 42204 KB Output is correct
49 Correct 680 ms 42204 KB Output is correct