Submission #1133183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133183		irmuun	나일강 (IOI24_nile)	C++20	100 / 100	476 ms	46248 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
 
const ll maxn=1e5+5,inf=2e9;
 
ll n;
 
struct segtree{
    vector<ll>d;
    void init(ll n){
        d.resize(4*n);
        build(1,0,n-1);
    }
    void build(ll v,ll l,ll r){
        if(l==r){
            d[v]=inf;
            return;
        }
        ll m=(l+r)>>1;
        build(v*2,l,m);
        build(v*2+1,m+1,r);
        d[v]=min(d[v*2],d[v*2+1]);
    }
    ll query(ll v,ll l,ll r,ll L,ll R){
        if(L>R||l>R||L>r){
            return inf;
        }
        if(L<=l&&r<=R){
            return d[v];
        }
        ll m=(l+r)>>1;
        return min(query(v*2,l,m,L,R),query(v*2+1,m+1,r,L,R));
    }
    void update(ll v,ll l,ll r,ll pos,ll val){
        if(r<pos||pos<l){
            return;
        }
        if(l==r){
            d[v]=val;
            return;
        }
        ll m=(l+r)>>1;
        update(v*2,l,m,pos,val);
        update(v*2+1,m+1,r,pos,val);
        d[v]=min(d[v*2],d[v*2+1]);
    }
};
 
segtree sg,odd,even;
 
ll sum[maxn];
 
ll calc(ll l,ll r){
    ll res=sum[r+1]-sum[l];
    if((r-l+1)%2==1){
        ll mn=sg.query(1,0,n-1,l,r);
        if(l%2==0) mn=min(mn,even.query(1,0,n-1,l,r));
        if(l%2==1) mn=min(mn,odd.query(1,0,n-1,l,r));
        res+=mn;
    }
    return res;
}
 
vector<long long>calculate_costs(vector<int>w,vector<int>a,vector<int>b,vector<int>e){
    vector<ll>W,A,B,E;
    for(ll i=0;i<w.size();i++){
        W.pb(w[i]);
        A.pb(a[i]);
        B.pb(b[i]);
    }
    for(ll i=0;i<e.size();i++){
        E.pb(e[i]);
    }
    vector<array<ll,3>>box;
    ll N=W.size(),Q=E.size();
    n=N;
    for(ll i=0;i<N;i++){
        box.pb({W[i],A[i],B[i]});
    }
    sum[0]=0;
    sort(all(box));
    for(ll i=0;i<N;i++){
        sum[i+1]=sum[i]+(ll)box[i][2];
    }
    sg.init(N);
    odd.init(N);
    even.init(N);
    for(ll i=1;i<N-1;i++){
        sg.update(1,0,N-1,i,box[i][1]-box[i][2]);
    }
    for(ll i=0;i<N;i++){
        if(i%2==1){
            odd.update(1,0,N-1,i,box[i][1]-box[i][2]);
        }
        else{
            even.update(1,0,N-1,i,box[i][1]-box[i][2]);
        }
    }
    vector<array<ll,3>>event;
    for(ll i=1;i<N;i++){
        event.pb({box[i][0]-box[i-1][0],-2,i});
    }
    for(ll i=2;i<N;i++){
        event.pb({box[i][0]-box[i-2][0],-1,i});
    }
    for(ll i=0;i<Q;i++){
        event.pb({E[i],0,i});
    }
    sort(rall(event));
    ll ans=0;
    map<pair<ll,ll>,ll>value;
    set<pair<ll,ll>>range;
    range.insert({0,N-1});
    range.insert({N,N});
    value[{0,N-1}]=ans;
    range.insert({N,N});
    vector<ll>answer(Q);
    set<pair<ll,ll>>new_range;
    vector<ll>idx;
    new_range.insert({0,N-1});
    for(auto [_,t,i]:event){
        if(t==0){
            for(auto [l,r]:new_range){
                ll val=calc(l,r);
                value[{l,r}]=val;
                ans+=val;
            }
            for(ll i:idx){
                auto it=range.upper_bound({i,N});
                it--;
                ll l=(*it).ff,r=(*it).ss;
                ll val=calc(l,r);
                ans-=value[{l,r}];
                value[{l,r}]=val;
                ans+=val;
            }
            new_range.clear();
            idx.clear();
            answer[i]=ans;
        }
        if(t==-1){
            i--;
            sg.update(1,0,N-1,i,inf);
            idx.pb(i);
        }
        if(t==-2){
            auto it=range.upper_bound({i,N});
            it--;
            pair<ll,ll>p=*it;
            range.erase(it);
            ll l=p.ff,r=p.ss;
            new_range.erase({l,r});
            ans-=value[{l,r}];
            
            range.insert({l,i-1});
            range.insert({i,r});
            new_range.insert({l,i-1});
            new_range.insert({i,r});
        }
    }
    return answer;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18