Submission #647708

#	Time	Username	Problem	Language	Result	Execution time	Memory
647708		Ronin13	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	1424 ms	75120 KiB

fortune_telling2

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

int lsb(int x){
    return x & -x;
}
const int NMAX = 1e6 + 1;
vector <int> bit(NMAX);
int n;
void add(int v, int val){
    while(v < NMAX){
        bit[v] += val;
        v += lsb(v);
    }
}

int get(int pos){
    int sum = 0;
    while(pos){
        sum += bit[pos];
        pos -= lsb(pos);
    }
    return sum;
}

int sum(int l, int r){
    return get(r) - get(l - 1);
}

vector <int> t(4 * NMAX);

void update(int v, int l, int r, int pos, int val){
    if(l > pos || r < pos) return;
    if(l == r){
        t[v] = max(val, t[v]);
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v + 1, m + 1, r, pos, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}
int get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st) return 0;
    if(l >= st && r <= fin) return t[v];
    int m = (l + r) / 2;
    return max(get(2 * v, l, m, st, fin),
               get(2 * v + 1, m + 1, r, st, fin));
}
map <int,int> mp;

int main(){
    cin >> n;
    int k; cin >> k;
    int a[n + 1], b[n + 1];
    int cur[n + 1];
    vector <int> vec;
    for(int i= 1; i<= n; i++){
        cin >> a[i] >> b[i];
        vec.pb(a[i]);
        vec.pb(b[i]);
        if(a[i] <= b[i]) cur[i] = 1;
        else cur[i] = 0;
    }
    int t[k + 1];
    for(int i = 1; i <= k; i++)
        cin >> t[i];
    for(int i = 1; i <= k; i++)
        vec.pb(t[i]);
    sort(vec.begin(), vec.end());
    for(int i = 0; i < vec.size(); i++){
        int x = vec[i];
        mp[x] = i + 1;
    }
    for(int i = k; i >= 1; i--){
        int v = t[i]; v = mp[v];
        update(1, 1, 2 * n + k, v, i);
    }
    ll ans = 0;
    vector <vector <int> > qv(2 * n + k + 1);
    for(int i = 1; i <= n; i++){
        int v = min(a[i], b[i]);
        int u = max(a[i], b[i]);
        int x = mp[v], y = mp[u]; y--;
        int val = get(1, 1, 2 * n + k, x, y);
        //cout << val << "\n";
        qv[val].pb(i);
    }
    for(int i = k; i >= 1; i--){
        int x= t[i]; x = mp[x];
        add(x, 1);
        for(int to : qv[i]){
            int r = max(b[to], a[to]); r= mp[r];
            int v = sum(r, NMAX - 1);
            //cout << v << ' ' ;
            if(v % 2 == 0) ans += (ll)max(b[to], a[to]);
            else ans += (ll)min(b[to], a[to]);
        }
        //cout << "\n";
    }
    for(int to : qv[0]){
        int r = max(b[to], a[to]); r = mp[r];
        int v = sum(r, NMAX - 1);
        v += cur[to];
        if(v & 1) ans += (ll)min(b[to], a[to]);
        else ans += (ll)max(b[to], a[to]);
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 0; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~

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