Submission #1195516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195516		enzy	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	1342 ms	129916 KiB

fortune_telling2

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+3;
const int inf=1e15+7;
int a[maxn], b[maxn], t[maxn], last[maxn], seg[4*maxn], qm[maxn], qnd[maxn], v[maxn];
map<int,int>relaciona, disrelaciona;
void update(int id, int ini, int fim, int cara, int val){
    if(ini==fim){
        seg[id]=val;
        return;
    }
    int mid=(ini+fim)/2, e=2*id, d=2*id+1;
    if(cara<=mid) update(e,ini,mid,cara,val);
    else update(d,mid+1,fim,cara,val);
    seg[id]=max(seg[e],seg[d]);
}
int query(int id, int ini, int fim, int l, int r){
    if(ini>r||fim<l) return 0;
    if(l<=ini&&fim<=r) return seg[id];
    int mid=(ini+fim)/2, e=2*id, d=2*id+1;
    return max(query(e,ini,mid,l,r),query(d,mid+1,fim,l,r));
}
int bit[3*maxn];
void add(int id){
    for(int i=id;i<3*maxn;i+=(i&-i)) bit[i]++;
}
int sum(int id){
    int ret=0;
    for(int i=id;i>0;i-=(i&-i)) ret+=bit[i];
    return ret;
}
signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, k; cin >> n >> k;
    set<int>comp;
    for(int i=1;i<=n;i++){
        cin >> a[i] >> b[i]; comp.insert(a[i]); comp.insert(b[i]);
    }
    vector<pair<int,int>>process;
    for(int i=1;i<=k;i++){
        cin >> t[i]; comp.insert(t[i]);
    }
    int cnt=0;
    for(int x : comp){
        cnt++;
        relaciona[x]=cnt;
        disrelaciona[cnt]=x; // para ter a soma original de volta qnd imprimir
    }
    // comprimindo as coordenadas
    for(int i=1;i<=n;i++) a[i]=relaciona[a[i]];
    for(int i=1;i<=n;i++) b[i]=relaciona[b[i]];
    for(int i=1;i<=k;i++) t[i]=relaciona[t[i]];
    // agr tds os caras são a[i],b[i],t[j]<=600.000=2*N+K, qtd de caras distintos
    for(int i=1;i<=k;i++) process.push_back({t[i],i});
    int idx=0;
    sort(process.begin(),process.end());
    for(pair<int,int> p : process){ // passando por t[j] crescente, e colocando na seg o indice do cara
        idx++;
        update(1,1,k,idx,p.second);
        v[idx]=p.first;
    }
    v[idx+1]=inf;
    vector<pair<int,int>>final;
    for(int i=1;i<=n;i++){
        int x=lower_bound(v+1,v+2+k,min(a[i],b[i]))-v;
        int y=lower_bound(v+1,v+2+k,max(a[i],b[i]))-v;
        // auto x=process.lower_bound({min(a[i],b[i]),0}), y=process.lower_bound({max(a[i],b[i]),0});
        // x eh o primeiro valor q troca o min(a[i],b[i])
        // y eh o primeiro valor q troca o max(a[i],b[i])
        // logo y-1 eh o ultimo cara q troca apenas o min(a[i],b[i]) 
        // mas se x==y, ent significa q n existe cara q troca apenas uma das faces e n a outra
        if(x==y) last[i]=0;
        else{
            y--;
            int l=x, r=y;
            last[i]=query(1,1,k,l,r);// qual foi a ultima vez, q eu tive um j, t.q. min(a[i],b[i])<=t[j]<max(a[i],b[i])
            //cout << i << " " << last[i] << " " << l << " " << r << endl;
        }
        final.push_back({last[i],i});
    }
    sort(final.begin(),final.end());
    int resp=0;
    for(int i=k;i>=1;i--){
        while(final.size()&&final.back().first>=i){ // já posso contar qnts caras tiveram dps da última vez q foi o maior
            int id=final.back().second;
            qnd[id]=i;
            if(a[id]<b[id]) swap(a[id],b[id]);
            int qtd=sum(3*maxn-1)-sum(a[id]-1);
            if(qtd%2) resp+=disrelaciona[b[id]];
            else resp+=disrelaciona[a[id]];
            if(qtd%2) qm[id]=disrelaciona[b[id]];
            else qm[id]=disrelaciona[a[id]];
            final.pop_back();
            //cout << resp << " " << qm[id] << endl;
        }
        add(t[i]);
    }
    while(final.size()){ // já posso contar qnts caras tiveram dps da última vez q foi o maior
        // nesse caso, n existe j, t.q. min(a[i],b[i])<=t[j]<max(a[i],b[i]), ent tds as operações funcionam nos dois 
        int id=final.back().second;
        int qtd=sum(3*maxn-1)-sum(max(a[id],b[id])-1);
        if(qtd%2) resp+=disrelaciona[b[id]];
        else resp+=disrelaciona[a[id]];
        if(qtd%2) qm[id]=disrelaciona[b[id]];
        else qm[id]=disrelaciona[a[id]];
        final.pop_back();
        //cout << resp << " " << qm[id] << endl;
    }
    /*for(int i=1;i<=n;i++) cout << qm[i] << " ";
    cout << endl;
    for(int i=1;i<=n;i++) cout << qnd[i] << " ";
    cout << endl;*/
    cout << resp << endl;
    return 0;
}

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