답안 #52182 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52182	2018-06-24T14:17:43 Z	`مرحبا بالعالم`(#1336)	운세 보기 2 (JOI14_fortune_telling2)	C++11	100 / 100	1525 ms	42204 KB

fortune_telling2

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #52182

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 65.0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
65.0 / 65.0