oj.uz

Submission #636066

# Submission time Handle Problem Language Result Execution time Memory
636066 2022-08-27T21:49:23 Z MasterTaster Fortune Telling 2 (JOI14_fortune_telling2) C++14
0 / 100
 3000 ms 340 KB 
#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;
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;
}
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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3098 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3098 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3098 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -