Submission #656755

#	Time	Username	Problem	Language	Result	Execution time	Memory
656755		uylulu	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	1136 ms	89852 KiB

fortune_telling2

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

#define ld long double
#define ll long long
#define endl "\n"

const int N = 6e5 + 100,K = 20;

int a[N + 1],b[N + 1];
int val[N + 1],lst[N + 1],cnt = 0;
int sparse[N + 1][K + 1],lg[N + 1];

bool sign[N + 1];

map<int,int> mp;
vector<int> query;

int bit[N + 1];

void add(int pos) {
    while(pos > 0) {
        bit[pos]++;
        pos -= pos&(-pos);
    }
}

int queryBIT(int pos) {
    int res = 0;
    for(int i = pos;i <= cnt;i += i&(-i)) {
        res += bit[i];
    }
    return res;
}

void buildSP() {
    for(int i = 2;i <= N;i++) {
        lg[i] = lg[i/2] + 1;
    }
    for(int i = 0;i <= cnt;i++) {
        sparse[i][0] = lst[i];
    }
    for(int j = 1;j <= K;j++) {
        for(int i = 0;i + (1<<j) <= N;i++) {
            sparse[i][j] = max(sparse[i][j - 1],sparse[i + (1<<(j - 1))][j - 1]);
        }
    }
}

int querySP(int l,int r) {
    int len = lg[r - l + 1];
    return max(sparse[l][len],sparse[r - (1<<len) + 1][len]);
}

signed main() {
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int n,k;
    cin>>n>>k;
    for(int i = 1;i <= n;i++) {
        cin>>a[i]>>b[i];
        sign[i] = 0;
        if(a[i] > b[i]) {
            sign[i] = 1;
            swap(a[i],b[i]);
        }
        mp[a[i]] = -1;
        mp[b[i]] = -1;
    }
    for(int i = 0;i < k;i++) {
        int x;
        cin>>x;
        mp[x] = -1;
        query.push_back(x);
    }

    for(auto u : mp) {
        mp[u.first] = cnt;
        val[cnt] = u.first;
        cnt++;
    }
    for(int i = 1;i <= n;i++) {
        a[i] = mp[a[i]];
        b[i] = mp[b[i]];
    }
    for(int i = 0;i < query.size();i++) {
        query[i] = mp[query[i]];
    }
    for(int i = 0;i <= cnt;i++) {
        lst[i] = -1;
    }
    for(int i = 0;i < query.size();i++) {
        lst[query[i]] = max(lst[query[i]],i);
    }
    mp.clear();

    ll res = 0;
    buildSP();

    vector<pair<int,int>> asd;
    
    for(int i = 1;i <= n;i++) {
        if(a[i] == b[i]) {
            res += val[a[i]];
            continue;
        }
        int nw = querySP(a[i],b[i] - 1);
        asd.push_back({nw + 1,i});
    }
    
    sort(asd.begin(),asd.end());
    reverse(asd.begin(),asd.end());

    int ptr = query.size() - 1;

    for(auto u : asd) {
        while(ptr >= u.first) {
            add(query[ptr]);
            ptr--;
        }
        int w = sign[u.second];
        if(u.first > 0) {
            w = 1;
        }

        int cnt = queryBIT(b[u.second]);
        w ^= (cnt%2);

        if(w == 0) {
            res += val[a[u.second]];
        } else {
            res += val[b[u.second]];
        }
    }
    cout<<res<<endl;

    return 0;
}

Compilation message (stderr)

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

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