제출 #1138722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138722		t9unkubj	Holiday (IOI14_holiday)	C++20	23 / 100	132 ms	9544 KiB

holiday

#ifdef t9unkubj
#define _GLIBCXX_DEBUG
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
using S=pair<ll,ll>;
S e(){
    return {0,0};
}
S op(S a,S b){
    return S{a.first+b.first,a.second+b.second};
}
struct segtree{
    int n;
    vc<S>node;
    segtree(int n_){
        int N=1;
        while((1<<N)<n_)N++;
        n=1<<N;
        node=vc<S>(n*2);
    }
    void set(int i,S x){
        node[i+=n]=x;
        while(i>>=1)node[i]=op(node[i*2],node[i*2+1]);
    }
    ll dive(int i,ll sm,int now,int k){
        if(i>=2*n)return sm;
        if(node[i].second+now<=k){
            now+=node[i].second;
            sm+=node[i].first;
            return dive((i+1)*2,sm,now,k);
        }
        return dive(i*2,sm,now,k);
    }
    ll kth(int k){
        if(node[1].second<=k)return node[1].first;
        return dive(2,0,0,k);
    }
};
#include"holiday.h"
ll solve(int n,int s,int d,vc<int>a){
    ll Ans=0;
    rep(t,2){
        //往復しない
        {
            ll now_sum=0;
            priority_queue<int,vc<int>,greater<>>que;
            for(int i=s;i<n;i++){
                que.push(a[i]);
                now_sum+=a[i];
                while(que.size()&&que.size()>d-(i-s)){
                    now_sum-=que.top();
                    que.pop();
                }
                chmax(Ans,now_sum);
            }
        }

        //s>i>j
        {
            vc<int>idx(n);
            iota(all(idx),0);
            sort(all(idx),[&](int i,int j){
                return a[i]>a[j];
            });
            vc<int>inv(n);
            rep(i,n){
                inv[idx[i]]=i;
            }

            vc<ll>ans(n,-4e18);            
            vc<int>best(n);
            vc<int>used(n);
            vc<array<int,5>>wait;
            int L=s/2;
            //(idx,best_l,best_r,l,r) best_l  <= \argmax score[idx][j]  best_r
            if(s)wait.push_back({(s+L)/2,0,n-1,L,s}),used[(s+L)/2]=1;
            
            
            while(wait.size()){
                segtree seg(n);
                auto push=[&](int i){
                    seg.set(inv[i],{a[i],1});
                };
                auto erase=[&](int i){
                    seg.set(inv[i],e());
                };
                sort(all(wait));
                dbg("CHECK"s);
                for(auto&x:wait)dbg(x[0],x[1],x[2],x[3],x[4]);
                int sl=0,sr=-1;

                for(auto&[i,tl,tr,l,r]:wait){
                    chmax(tl,i);
                    chmax(tr,i);
                    while(sr!=tl){
                        push(++sr);
                    }
                    while(sl!=i){
                        erase(sl++);
                    }
                    while(1){
                        if(i==1)dbg(sl,sr,tl,tr);
                        int W=(s-i)+(sr-i);
                        if(W>d)break;
                        if(i==1)dbg(seg.kth(d-W));
                        if(chmax(ans[i],seg.kth(d-W))){
                            best[i]=sr;
                        }
                        if(sr==tr)break;
                        push(++sr);
                    }
                }

                decltype(wait) nxt;
                auto make=[&](int x,int tl,int tr,int l,int r){
                    chmin(tl,tr);
                    if(x<n&&!used[x]){
                        used[x]=1;
                        nxt.push_back({x,tl,tr,l,r});
                    }
                };
                for(auto&[x,tl,tr,l,r]:wait){
                    make((l+x)/2,tl,best[x],l,x);
                    make((r+x)/2,best[x],tr,x,r);
                }
                wait=move(nxt);
    
            }
            chmax(Ans,*max_element(all(ans)));
        } 
        s=n-1-s;
        reverse(all(a));
    }
    return Ans;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    vc<int>a(n);
    rep(i,n)a[i]=attraction[i];
    return solve(n,start,d,a);
}
void run(){
    mt19937 mt;
    {
        int n=mt()%20+1;
        int s=mt()%n;
        int d=mt()%(n*2);
        vc<int>a(n);
        rep(i,n)a[i]=mt();
        rep(i,n)a[i]=abs(a[i]);
        solve(n,s,d,a);
    }
}
/*
int main(){
    #ifdef t9unkubj
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    run();
}*/

• Subtask 1: 0 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53