제출 #1215258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1215258		ASGA_RedSea	봉쇄 시간 (IOI23_closing)	C++17	0 / 100	193 ms	49152 KiB

closing

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll=long long;

#include"closing.h"

int max_score(int n,int x,int y,ll k,vector<int>U,vector<int>V,vector<int>W);


struct sgt{
    vector<ll>s,c;
    int lg,sz;
    sgt(int n){
        lg=__lg(n)+1;
        sz=1<<lg;
        s.assign(sz*2,0);c=s;
    }
    void add(int i,ll v){
        i+=sz;
        assert(s[i]==0);
        s[i]+=v;
        c[i]=1;
        while(i>1){
            i>>=1;
            s[i]=s[i*2]+s[i*2+1];
            c[i]=c[i*2]+c[i*2+1];
        }
    }
    void del(int i){
        i+=sz;s[i]=c[i]=0;
        while(i>1){
            i>>=1;
            s[i]=s[i*2]+s[i*2+1];
            c[i]=c[i*2]+c[i*2+1];
        }
    }
    ll get(ll L,ll R,ll l,ll r,ll i){
        if(l>R||L>r)return 0;
        if(L<=l&&r<=R)return c[i];
        return get(L,R,l,(l+r)/2,i*2)+get(L,R,(l+r)/2+1,r,i*2+1);
    }
    ll get(ll k){
        ll i=1,tot=0;
        while(i<sz){
            if(tot+s[i*2]<=k){tot+=s[i*2];i=i*2+1;}
            else i*=2;
        }
        if(s[i]+tot<=k)i++;

        return i-sz-get(1,i-sz,1,sz,1);
    }
};

const ll inf=1e18;

int max_score(int n,int x,int y,ll k,vector<int>U,vector<int>V,vector<int>W){
    vector<vector<array<ll,2>>>a(n);
    int sbt=1;
    for(int i=0;i+1<n;i++){
        a[U[i]].push_back({V[i],W[i]});
        a[V[i]].push_back({U[i],W[i]});
        sbt&=V[i]==U[i]+1;
    }

    ll ans=0;

    queue<int>q;
    vector<array<ll,2>>d(n,{inf,inf});

    d[x][0]=0;q.push(x);
    while(!q.empty()){
        int i=q.front();q.pop();
        for(auto&[j,w]:a[i]){
            if(d[j][0]==inf){d[j][0]=d[i][0]+w;q.push(j);}
        }
    }
    d[y][1]=0;q.push(y);
    while(!q.empty()){
        int i=q.front();q.pop();
        for(auto&[j,w]:a[i]){
            if(d[j][1]==inf){d[j][1]=d[i][1]+w;q.push(j);}
        }
    }

    vector<int>vis(n,0);
    multiset<array<ll,2>>s;
    for(int i=0;i<n;i++){
        s.insert({d[i][0],i});
        s.insert({d[i][1],i});
    }

    ll kk=k;
    for(int cnt=0;cnt<n;cnt++){
        ll i=(*s.begin())[1],c=(*s.begin())[0];
        s.erase(s.find(*s.begin()));
        if(vis[i]||c>kk)break;
        vis[i]++;
        kk-=c;ans++;
    }


    if(sbt){
        vector<ll>p(n,0);
        for(int i=0;i+1<n;i++)p[i+1]=p[i]+a[i][(a[i][1][0]==i+1)][1];

        auto dis=[&](int i,int j)->ll{
            if(i>j)swap(i,j);
            return p[j]-p[i];
        };

        for(int l=0;l<=y;l++){
            int r=max(x,l);

            ll v=0;

            for(int i=l;i<=r;i++)v+=max(dis(i,x),dis(i,y));
            for(int i=r+1;i<=y;i++)v+=dis(i,y);
            for(int i=x;i<l;i++)v+=dis(i,x);



            vector<ll>vl;
            for(int i=0;i<min(l,x);i++)vl.push_back(dis(i,x));
            for(int i=max(y,r)+1;i<n;i++)vl.push_back(dis(i,y));

            sort(vl.begin(),vl.end());
            map<ll,vector<int>>val;
            for(int i=0;i<vl.size();i++)val[vl[i]].push_back(i);

            map<ll,int>c;

            sgt s(vl.size());
            for(int i=0;i<vl.size();i++)s.add(val[vl[i]][c[vl[i]]++],vl[i]);

            c.clear();

            if(v<=k)ans=max(ans,(r-l+1)*2+max(0,l-x)+max(0,y-r)+s.get(k-v));


            while(++r<n){
                if(r<=y)v+=max(0LL,dis(r,x)-dis(r,y));
                else v+=dis(r,x);


                if(r>y)s.del(val[dis(r,y)][c[dis(r,y)]++]);
                if(v<=k)ans=max(ans,(r-l+1)*2+max(0,l-x)+max(0,y-r)+s.get(k-v));
            }
        }


        return ans;
    }
    assert(0);


    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17