Submission #422606

#	Time	Username	Problem	Language	Result	Execution time	Memory
422606		ACmachine	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	541 ms	40488 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
const int INF = (int)1e9;
typedef long long ll;
struct segmax{
    vector<int> tree;
    int n;
    segmax(int sz, vector<int> &init){
        n = 1; 
        while(n < sz) n *= 2;
        tree.resize(2 * n, -INF);
        REP(i, n){
            if(i < init.size()){
                tree[i + n] = init[i];
            }
        }
        FORD(i, n - 1, 1, 1){
            tree[i] = max(tree[i << 1], tree[i << 1 | 1]);
        }
    }
    int query(int l, int r, int beg, int end, int v){
        if(beg >= l && end <= r){
            return tree[v];
        }
        if(beg >= r || end <= l)
            return -INF;
        int mid = (beg + end) >> 1;
        return max(query(l, r, beg, mid, v << 1), query(l, r, mid, end, v << 1 | 1));
    }
};
// for offline get number of elements > x in segment [l, r];
struct segsum{
    vector<int> tree;
    int n;
    segsum(int sz){
        n = 1; 
        while(n < sz) n *= 2;
        tree.resize(2 * n, 0); 
    }
    int query(int l, int r, int beg, int end, int v){
        if(beg >= l && end <= r){
            return tree[v];
        }
        if(beg >= r || end <= l)
            return 0;
        int mid = (beg + end) >> 1;
        return query(l, r, beg, mid, v << 1) + query(l, r, mid, end, v << 1 | 1);
    }
    void upd(int pos, int val){
        pos += n;
        tree[pos] += val;
        for(int i = pos / 2; i > 0; i /= 2){
            tree[i] = tree[i << 1] + tree[i << 1 | 1];
        }
    }
};
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    const int mx = 700000;
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    vector<int> comp;
    REP(i, n){
        cin >> a[i] >> b[i];        
        comp.pb(a[i]);
        comp.pb(b[i]);
    }
    vector<int> t(k);
    REP(i, k){
        cin >> t[i];
        comp.pb(t[i]);
    }
    vector<int> oa = a, ob = b, ot = t; // to get sum later
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    REP(i, n){
        a[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin();
        b[i] = lower_bound(comp.begin(), comp.end(), b[i]) - comp.begin();
    }
    REP(i, k){
        t[i] = lower_bound(comp.begin(), comp.end(), t[i]) - comp.begin(); 
    }
    vector<int> numflips(n, 0);
    vector<int> determined_side(n, 0); // which side is it after finding the last one that determines;that is biggest j,so that T[j] >= a && t[j] < b
    vector<int> initmax(mx, -INF);
    REP(i, k){
        initmax[t[i]] = max(initmax[t[i]], i);
    }
    segmax st(mx, initmax);
    
    struct query{
        int x, tl, query_index, sign; 
        bool operator<(query &oth){
            return tie(x, tl, query_index, sign) < tie(oth.x, oth.tl, oth.query_index, sign);
        }
    };
    vector<query> queries;
    REP(i, n){
        int f = a[i], s = b[i];
        if(f > s) swap(f, s);
        int l = -INF, r = mx; // get number of j, to that t[j] >= max(a[i], b[i]) and index > x; go in order of j, add to segsum at t[j]; 
        // [l, r) are based on indices
        if(f != s){
            l = st.query(f, s, 0, st.n, 1);
            if(l != -INF){
                if(f == a[i])
                    determined_side[i] = 1; 
            }
        }
        queries.pb({l, max(a[i], b[i]), i, -1});
        queries.pb({r, max(a[i], b[i]), i, 1});
    }
    segsum ft(mx);
    sort(queries.begin(), queries.end());
    int pp = 0;
    REP(i, t.size() + 1){
        while(pp < queries.size() && ((queries[pp].x <= i) || (i == (int)t.size()))){ // ans queries
            auto que = queries[pp];
            int ans = ft.query(que.tl, mx, 0, ft.n, 1);
            ans *= que.sign;
            numflips[que.query_index] += ans;
            pp++;
        }
        if(i == (int)t.size()) 
            break;
        ft.upd(t[i], 1);
    }
    ll sum = 0;
    REP(i, n){
        int side = determined_side[i];
        side ^= (numflips[i] % 2);
        if(side == 0) 
            sum += oa[i];
        else
            sum += ob[i];
    }
    cout << sum << "\n";
}

Compilation message (stderr)

fortune_telling2.cpp: In constructor 'segmax::segmax(int, std::vector<int>&)':
fortune_telling2.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |             if(i < init.size()){
      |                ~~^~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:4:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
fortune_telling2.cpp:6:19: note: in expansion of macro 'FOR'
    6 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
fortune_telling2.cpp:124:5: note: in expansion of macro 'REP'
  124 |     REP(i, t.size() + 1){
      |     ^~~
fortune_telling2.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         while(pp < queries.size() && ((queries[pp].x <= i) || (i == (int)t.size()))){ // ans queries
      |               ~~~^~~~~~~~~~~~~~~~

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