Submission #636059

#	Time	Username	Problem	Language	Result	Execution time	Memory
636059		MasterTaster	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	4 / 100	3080 ms	5416 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[4*MAXN+5], seg[12*MAXN];
bool sw[MAXN];
pii c[MAXN];
vector<pii> tmp;

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<MAXN)
    {
        bit[x]+=val;
        x+=x&(-x);
    }
    return;
}
int sum(int x)
{
    if (x<=0) return 0;
    int ret=0;
    while (x)
    {
        ret+=bit[x];
        x-=x&(-x);
    }
    return ret;
}

int main() {
    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;
    multiset<int> s;
    for (int i=k; i>=0; i--)
    {
        ///cout<<"i "<<i<<endl;
        if (i) s.insert(t[i]);
        while (j>=0 && tmp[j].xx==i) { /*cout<<i<<" ij "<<j<<endl;*/ cnt[tmp[j].yy]=distance(s.begin(), s.lower_bound(a[tmp[j].yy])); 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;
}

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