Submission #445183

#	Time	Username	Problem	Language	Result	Execution time	Memory
445183		JovanB	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	792 ms	64072 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
int a[200005];
int b[200005];
int sp[25][200005];
int g[200005];
int treba[200005];
int lg[200005];
int bit[600005];
 
pair <int, int> t[200005];
 
int k;
 
int nadji(int x){
    /// poslednji manji jednak x
    int l = 1, r = k, res = 0;
    while(l <= r){
        int mid = (l+r)/2;
        if(t[mid].first <= x){
            l = mid+1;
            res = mid;
        }
        else r = mid-1;
    }
    return res;
}
 
int getmax(int l, int r){
    int j = lg[r-l+1];
    return max(sp[j][l], sp[j][r-(1<<j)+1]);
}
 
int bitget(int x){
    int res = 0;
    while(x){
        res += bit[x];
        x -= x & -x;
    }
    return res;
}
 
void bitadd(int x){
    while(x <= 600000){
        bit[x]++;
        x += x & -x;
    }
}
 
map <int, int> u;
vector <int> vec[200005];
int kolko[200005];
 
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;
 
    int n;
    cin >> n >> k;
    for(int i=2; i<=k; i++){
        lg[i] = 1 + lg[i/2];
    }
    for(int i=1; i<=n; i++){
        cin >> a[i] >> b[i];
    }
    for(int i=1; i<=k; i++){
        cin >> t[i].first;
        t[i].second = i;
        g[i] = t[i].first;
    }
    sort(t+1, t+1+k);
    for(int i=1; i<=k; i++){
        sp[0][i] = t[i].second;
    }
    for(int j=1; (1<<j)<=k; j++){
        for(int i=1; i+(1<<j)-1<=k; i++){
            sp[j][i] = max(sp[j-1][i], sp[j-1][i+(1<<(j-1))]);
        }
    }
    for(int i=1; i<=n; i++){
        int p = min(a[i], b[i]);
        int d = max(a[i], b[i]);
        int x = nadji(p-1);
        int y = nadji(d-1);
        if(x >= y) continue;
        treba[i] = getmax(x+1, y);
    }
    vector <int> comp;
    for(int i=1; i<=n; i++){
        vec[treba[i]+1].push_back(i);
    }
    for(int i=1; i<=n; i++){
        comp.push_back(a[i]);
        comp.push_back(b[i]);
    }
    for(int i=1; i<=k; i++){
        comp.push_back(g[i]);
    }
    sort(comp.begin(), comp.end());
    int cmpr = 0;
    for(auto c : comp){
        if(!u[c]) u[c] = ++cmpr;
    }
    for(int i=k; i>=1; i--){
        bitadd(u[g[i]]);
        for(auto c : vec[i]){
            kolko[c] = k-i+1 - bitget(u[min(a[c], b[c])]);
        }
    }
    ll res = 0;
    for(int i=1; i<=n; i++){
        //cout << i << " " << treba[i] << " " << kolko[i] << endl;
        kolko[i] %= 2;
        if(a[i] >= b[i] || treba[i] == 0){
            if(kolko[i]) res += b[i];
            else res += a[i];
        }
        else{
            if(kolko[i]) res += a[i];
            else res += b[i];
        }
    }
    cout << res;
    return 0;
}

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