Submission #1065158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065158		boyliguanhan	Closing Time (IOI23_closing)	C++17	100 / 100	681 ms	98356 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const int M=1<<20;
struct helper_class {
    struct BIT {
        private:
        set<int>todie;
        ll TRE[M];
        int cnt[M];
        ll qryvl(int i){
            ll res=0;
            while(i)
                res+=TRE[i],i-=i&-i;
            return res;
        }
        int querycnt(int i){
            int res=0;
            while(i)res+=cnt[i],
                i-=i&-i;
            return res;
        }
        public:
        void upd(int i,ll v,int cof){
            while(i<1e6) todie.insert(i),
                cnt[i]+=cof,TRE[i]+=cof*v,i+=i&-i;
        }
        int howmuch(ll v){
            int l=0,r=1e6,res=0;
            while(l<=r){
                int mid=l+r>>1;
                if(qryvl(mid)<=v)
                    res=mid,l=mid+1;
                else r=mid-1;
            }
            return querycnt(res);
        }
        void reset(){
            for(auto i:todie)
                TRE[i]=cnt[i]=0;
            todie.clear();
        }
    } cur;
    int operator()(vector<pair<ll,ll>> V,ll K){
        cur.reset();
        if(K<0) return -1e9;
        map<ll,int>mp;
        for(auto&[i,j]:V)swap(i,j);
        sort(V.begin(),V.end());
        for(auto&[i,j]:V)swap(i,j);
        for(auto[i,j]:V)
            mp[i]++,mp[j-i]++;
        int ans=0,CC=0,n=V.size();
        for(auto&[i,j]:mp)
            j=CC+=j;
        vector<pair<int,int>> v2;
        for(auto[i,j]:V)
            v2.push_back({mp[i]--,mp[j-i]--});
        for(int i=0;i<n;i++)
            cur.upd(v2[i].first,V[i].first,1);
        ans=cur.howmuch(K);
        for(int i=0;i<n;){K-=V[i].first; if(K<0)break;
            cur.upd(v2[i].first,V[i].first,-1);
            cur.upd(v2[i].second,V[i].second-V[i].first,1);
            ans=max(ans,++i+cur.howmuch(K));
        }
        return ans;
    }
} thecenter;
vector<pair<int,int>>adj[M];
vector<ll>v;
vector<int>path;
ll dis[M][2];
void dfs(int n,int p,ll d,int k){
    dis[n][k]=d;
    v.push_back(d);
    for(auto[i,w]:adj[n])
        if(i-p)dfs(i,n,d+w,k);
}
int max_score(int N, int X, int Y, ll K,std::vector<int> U, std::vector<int> V, std::vector<int> W){
    for(int i=0;i<N-1;i++)
        adj[U[i]].push_back({V[i],W[i]}),
        adj[V[i]].push_back({U[i],W[i]});
    v.clear();
    dfs(X,N,0,0);
    dfs(Y,N,0,1);
    sort(v.rbegin(),v.rend());
    ll origK=K;
    while(v.size())
        if(v.back()<=K)
            K-=v.back(),
            v.pop_back();
        else break;
    for(int i=0;i<N;i++)
        adj[i].clear();
    K=origK;
    int ans1=2*N-v.size();
    vector<pair<ll,ll>> stuf;
    for(int i=0;i<N;i++)
        if(dis[i][0]+dis[i][1]==dis[X][1])
            K-=min(dis[i][0],dis[i][1]),
            stuf.push_back({0,abs(dis[i][0]-dis[i][1])});
        else stuf.push_back({min(dis[i][0],dis[i][1]),
                            max(dis[i][0],dis[i][1])});
    return max(ans1,thecenter(stuf,K));
}

Compilation message (stderr)

closing.cpp: In member function 'int helper_class::BIT::howmuch(ll)':
closing.cpp:33:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |                 int mid=l+r>>1;
      |                         ~^~

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