Submission #636129

#	Time	Username	Problem	Language	Result	Execution time	Memory
636129		MasterTaster	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	349 ms	18732 KiB

fortune_telling2

#include <iostream>
#include <vector>
#include <set>
#include <iterator>
#include <algorithm>
 
#define ll long long
#define MAXN 200010
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
 
using namespace std;
 
int n, k, a[MAXN], b[MAXN], t[MAXN], last[MAXN];
int cnt[MAXN];
int bit[3*MAXN+5], seg[4*MAXN+10];
bool sw[MAXN];
pii c[MAXN];
vector<pii> tmp;
vector<int> svi;
 
void build(int node, int l, int r)
{
    if (l==r) { seg[node]=c[l].yy; return; }
 
    int mid=l+(r-l)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    seg[node]=max(seg[2*node], seg[2*node+1]);
}
int maxQuery(int node, int l, int r, int levo, int desno)
{
    if (levo>r ||  desno<l) return -1;
    if (levo<=l && desno>=r) return seg[node];
 
    int mid=l+(r-l)/2;
    return max(maxQuery(2*node, l, mid, levo, desno),
               maxQuery(2*node+1, mid+1, r, levo, desno));
}
 
void upd(int x, int val)
{
    while (x<3*MAXN)
    {
        bit[x]+=val;
        x+=x&(-x);
    }
}
int sum(int x)
{
    if (x<=0) return 0;
    int ret=0;
    while (x)
    {
        ret+=bit[x];
        x-=x&(-x);
    }
    return ret;
}
int binarna(int x)
{
    int ret=distance(svi.begin(), lower_bound(svi.begin(), svi.end(), x));
    return (ret+1);
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    cin>>n>>k;
 
    for (int i=1; i<=n; i++) { cin>>a[i]>>b[i]; if (a[i]>b[i]) { sw[i]=true; swap(a[i], b[i]); } }
 
    for (int i=1; i<=k; i++) cin>>t[i];
 
    for (int i=1; i<=k; i++) { pii par={t[i], i}; c[i]=par; }
    sort(c+1, c+k+1);
 
    ///for (int i=1; i<=k; i++) { cout<<c[i].xx<<" "<<c[i].yy<<endl; }
 
    build(1, 1, k);
 
    for (int i=1; i<=n; i++) {
        pii minpar = {a[i], 0}, maxpar = {b[i], 0};
        int l = distance(c + 1, lower_bound(c + 1, c + k + 1, minpar));
        int r = distance(c + 1, lower_bound(c + 1, c + k + 1, maxpar));
        r--;
 
        l++; r++;
        ///cout<<i<<": "<<l<<" lr "<<r<<endl;
        if (l > r) last[i] = 0;
        else last[i] = maxQuery(1, 1, k, l, r);
    }
 
    for (int i=1; i<=n; i++) tmp.pb({last[i], i});
    sort(tmp.begin(), tmp.end()/*, greater<pii>()*/);
 
    ///for (int i=0; i<tmp.size(); i++) cout<<tmp[i].xx<<" tmp "<<tmp[i].yy<<endl;
 
    int j=tmp.size()-1;
 
    for (int i=1; i<=k; i++) svi.pb(t[i]);
    for (int i=1; i<=n; i++) svi.pb(a[i]);
    sort(svi.begin(), svi.end());
    auto it=unique(svi.begin(), svi.end());
    svi.resize(distance(svi.begin(), it));
    ///for (int i=0; i<svi.size(); i++) cout<<svi[i]<<" ";
    ///cout<<endl;
 
    //multiset<int> s;
    for (int i=k; i>=0; i--)
    {
        ///cout<<"i "<<i<<endl;
        if (i) { int x=binarna(t[i]); /*cout<<t[i]<<" "<<x<<endl;*/ upd(x, 1); }
        while (j>=0 && tmp[j].xx==i) { /*cout<<i<<" ij "<<j<<endl;*/ cnt[tmp[j].yy]=sum(binarna(a[tmp[j].yy])-1); j--; }
        ///cout<<j<<" j"<<endl;
    }
 
    ll ans=0;
    for (int i=1; i<=n; i++)
    {
        int kolko=k-last[i]-cnt[i];
        if (last[i]==0 && sw[i]) swap(a[i], b[i]);
        ///cout<<i<<" "<<last[i]<<" "<<cnt[i]<<endl;
        if (last[i]==0) { if (kolko%2) ans+=(ll)b[i]; else ans+=(ll)a[i]; }
        else { if (kolko%2) ans+=(ll)a[i]; else ans+=(ll)b[i]; }
        ///cout<<"ans "<<ans<<endl;
    }
    cout<<ans;
}

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