Submission #321160

#	Time	Username	Problem	Language	Result	Execution time	Memory
321160		lohacho	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	558 ms	26372 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)6e5 + 4;
int N, k;
int a[NS], b[NS];
int t[NS];
vector<int> srt;
int last[NS];
struct Data{
    int pos, mn, num;
    bool operator<(const Data&r)const{
        return pos > r.pos;
    }
}que[NS];

int seg[NS * 4];
void push(int num, int s, int e, int pos, int val){
    if(pos < s || pos > e) return;
    if(s == e){
        seg[num] = val;
        return;
    }
    push(num * 2, s, (s + e) / 2, pos, val), push(num * 2 + 1, (s + e) / 2 + 1, e, pos, val);
    seg[num] = max(seg[num * 2], seg[num * 2 + 1]);
}

int get(int num, int s, int e, int fs, int fe){
    if(fe < s || fs > e || fs > fe) return 0;
    if(s >= fs && e <= fe){
        return seg[num];
    }
    return max(get(num * 2, s, (s + e) / 2, fs, fe), get(num * 2 + 1, (s + e) / 2 + 1, e, fs, fe));
}

struct fenwick{
    vector < int > fenw;
    int N;
    fenwick(){}
    fenwick(int n):N(n){
        fenw.resize(N);
    }
    void push(int x, int val){
        for(int i = x; i < N; i += (i & -i)){
            fenw[i] += val;
        }
    }
    int get(int x){
        int rv = 0;
        for(int i = x; i; i -= (i & -i)){
            rv += fenw[i];
        }
        return rv;
    }
}fen(NS);

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> k;
    for(int i = 1; i <= N; ++i){
        cin >> a[i] >> b[i];
        srt.push_back(a[i]), srt.push_back(b[i]);
    }
    for(int i = 1; i <= k; ++i){
        cin >> t[i];
        srt.push_back(t[i]);
    }
    sort(srt.begin(), srt.end());
    srt.erase(unique(srt.begin(), srt.end()), srt.end());
    for(int i = 1; i <= N; ++i){
        a[i] = lower_bound(srt.begin(), srt.end(), a[i]) - srt.begin() + 1;
        b[i] = lower_bound(srt.begin(), srt.end(), b[i]) - srt.begin() + 1;
    }
    for(int i = 1; i <= k; ++i){
        t[i] = lower_bound(srt.begin(), srt.end(), t[i]) - srt.begin() + 1;
        last[t[i]] = i;
    }
    for(int i = 1; i <= (int)srt.size(); ++i){
        push(1, 1, (int)srt.size(), i, last[i]);
    }
    for(int i = 1; i <= N; ++i){
        int mn = min(a[i], b[i]), mx = max(a[i], b[i]);
        int pos = get(1, 1, (int)srt.size(), mn, mx - 1);
        que[i].pos = pos + 1, que[i].mn = mx, que[i].num = i;
    }
    sort(que + 1, que + N + 1);
    reverse(que + 1, que + N + 1);
    int j = N;
    LL ans = 0;
    for(int i = k; i >= 1; --i){
        while(j && que[j].pos > i){
//            cout << que[j].pos << ' ' << que[j].mn << ' ' << que[j].num << endl;
            int flip = fen.get((int)srt.size()) - fen.get(que[j].mn - 1);
            if(a[que[j].num] >= b[que[j].num]){
                if(flip % 2){
                    ans += srt[b[que[j].num] - 1];
                }
                else{
                    ans += srt[a[que[j].num] - 1];
                }
            }
            else{
                if(flip % 2){
                    ans += srt[a[que[j].num] - 1];
                }
                else{
                    ans += srt[b[que[j].num] - 1];
                }
            }
            --j;
//            cout << ans << endl;
        }
        fen.push(t[i], 1);
    }
    while(j){
//        cout << que[j].pos << ' ' << que[j].mn << ' ' << que[j].num << endl;
        int flip = fen.get((int)srt.size()) - fen.get(que[j].mn - 1);
        if(a[que[j].num] >= b[que[j].num]){
            if(flip % 2){
                ans += srt[b[que[j].num] - 1];
            }
            else{
                ans += srt[a[que[j].num] - 1];
            }
        }
        else{
            if((flip % 2 && que[j].pos > 1) || (flip % 2 == 0 && que[j].pos == 1)){
                ans += srt[a[que[j].num] - 1];
            }
            else{
                ans += srt[b[que[j].num] - 1];
            }
        }
        --j;
//        cout << ans << endl;
    }
    cout << ans;
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65