Submission #1100732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100732		RiverFlow	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	211 ms	27524 KiB

fortune_telling2

#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

void prepare(); void main_code();

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0; prepare();
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); }
}

void prepare() {};

template<typename T>
struct fenwick {
    int n; vector<T> bit; bool up = 0;
    fenwick() {};
    fenwick(int _n, bool _up) { n = _n; bit.resize(n + 7); up = _up; }
    void upd(int id, T val) {
        if (up) for(; id <= n; id += id & -id) bit[id] += val;
        else    for(; id  > 0; id -= id & -id) bit[id] += val;
    }
    T get(int id) {
        T ans = 0;
        if (up) for(; id  > 0; id -= id & -id) ans += bit[id];
        else    for(; id <= n; id += id & -id) ans += bit[id];
        return ans;
    }
};


const int LG = 17;

int sp[N][LG + 1];

int a[N], b[N], t[N];

void main_code() {
    int n, k; cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
    }
    for(int i = 1; i <= k; ++i) {
        cin >> t[i];
    }
    vector<pair<int, int>> o;
    FOR(i, 1, k) o.push_back(_mp(t[i], i));
    sort(all(o));
    FOR(i, 1, k) {
        sp[i][0] = o[i - 1].second;
    }
    vec<int> lg(k + 1, 0), luu(n + 1, 0);
    FOR(i, 2, k) lg[i] = lg[i / 2] + 1;
    FOR(j, 1, LG) if ( (1 << j) <= k ) {
        for(int i = 1; i + (1 << j) - 1 <= k; ++i) {
            sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
        }
    }

    auto get = [&](int l, int r){
        int j = lg[r - l + 1];
        return max(sp[l][j], sp[r - (1 << j) + 1][j]);
    };

    fenwick<int> bit(k, 0);

    FOR(i, 1, n) if (a[i] != b[i]) {
        int l = min(a[i], b[i]);
        int r = max(a[i], b[i]) - 1;
        if (o.back().fi < l) continue ;
        if (o[0].fi > r) continue ;
        int ll = lower_bound(all(o), _mp(l, 0)) - o.begin() + 1;
        int rr = (--upper_bound(all(o), _mp(r, INT_MAX))) - o.begin() + 1;
        if (ll <= rr) {
            luu[i] = get(ll, rr);
        }
    }
//    FOR(i, 1, n) cout << luu[i] << ' ' ; cout << nl;



    long long ans = 0;
    vec<ii> ev;
    FOR(i, 1, n) {
        if (a[i] == b[i]) {
            ans += a[i];
            continue ;
        }
        ev.push_back(_mp(max(b[i],a[i]),i));
    }
    FOR(i, 1, k) {
        ev.push_back(_mp(t[i], -i));
    }
    sort(ev.begin(), ev.end(), greater<ii>());
    int m = sz(ev);
    for(int i=0,j=0;i<m;++i){
        while(j+1<m and ev[j+1].fi==ev[i].fi)++j;
        FOR(k,i,j)if(ev[k].se<0){
            int p=-ev[k].se;
            bit.upd(p,1);
        }
        FOR(k,i,j)if(ev[k].se>0){
            //tra loi
            int p=ev[k].se;
            if (luu[p]==0){
                int t=bit.get(1);
                if(t % 2 == 0) ans += a[p];
                else ans += b[p];
            }else{
                int t=bit.get(luu[p]+1);
                if(t % 2 == 0) ans += max(a[p], b[p]);
                else ans += min(a[p], b[p]);
            }
        }
        i = j;
    }
    cout << ans;

}


/*     Let the river flows naturally     */

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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