Submission #656745

#	Time	Username	Problem	Language	Result	Execution time	Memory
656745		uylulu	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	35 / 100	1271 ms	262144 KiB

fortune_telling2

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

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

const int N = 5e5,K = 23;

int a[N + 1],b[N + 1],sign[N + 1];

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

vector<pair<int,int>> seg[4*N + 1];

void buildST(int id,int l,int r) {
    if(l == r) {
        seg[id] = {{query[l],1}};
        return;
    }
    int mid = (l + r)/2;
    buildST(id*2,l,mid);
    buildST(id*2 + 1,mid + 1,r);

    seg[id] = seg[id*2];
    for(auto u : seg[id*2 + 1]) {
        seg[id].push_back(u);
    }
    sort(seg[id].begin(),seg[id].end());
    
    for(int i = 0;i < seg[id].size();i++) {
        seg[id][i].second = i + 1;
    }
}

int queryST(int id,int l,int r,int u,int v,int val) {
    if(v < l || u > r) return 0;
    
    if(u <= l && v >= r) {
        auto it = lower_bound(seg[id].begin(),seg[id].end(),make_pair(val,(int)-1));
        if(it == seg[id].end()) return 0;

        return (seg[id].size()) - (*it).second + 1;
    }
    int mid = (l + r)/2;
    return queryST(id*2,l,mid,u,v,val) + queryST(id*2 + 1,mid + 1,r,u,v,val);
}

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

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) <= cnt + 1;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);
    }

    int res = 0;
    buildSP();
    buildST(1,0,query.size() - 1);

    // for(int i = 1;i <= n;i++) {
    //     cout<<a[i]<<" "<<b[i]<<endl;
    // }
    // for(auto u : query) {
    //     cout<<u<<endl;
    // }
    for(int i = 1;i <= n;i++) {
        if(a[i] == b[i]) {
            res += val[a[i]];
            continue;
        }
        // cout<<a[i]<<" "<<b[i]<<endl;
        int nw = querySP(a[i],b[i] - 1);

        int w = sign[i];
        if(nw != -1) w = 1;

        int cnt = queryST(1,0,query.size() - 1,nw + 1,query.size() - 1,b[i]);

        w ^= (cnt%2);

        if(w == 0) {
            res += val[a[i]];
            // cout<<val[a[i]]<<" "<<cnt<<" "<<nw<<endl;
        } else {
            res += val[b[i]];
            // cout<<val[b[i]]<<" "<<cnt<<" "<<nw<<endl;
        }
    }
    cout<<res<<endl;
    

    return 0;
}

Compilation message (stderr)

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

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