Submission #1293206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293206		hainam2k9	Nile (IOI24_nile)	C++20	100 / 100	123 ms	17168 KiB

nile

#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 1e5+5;
const string NAME = "";
int n;
ll sum=0,cur=0;
vector<pair<int,pair<int,int>>> v;
vector<ll> rs;
struct Artifact{
    ll w,a,b,pos,val;
    bool operator<(const Artifact& a) const{
        return w<a.w;
    }
}a[MAXN];
struct DSU{
    int par[MAXN],sz[MAXN];
    ll sum[MAXN],val[MAXN],MIN[MAXN][3];
    void init(int n){
        memset(MIN,0x3f,sizeof(MIN));
        for(int i = 1; i<=n; ++i)
            par[i]=i, sz[i]=1, sum[i]=a[i].val, MIN[i][i&1]=a[i].val;
    }
    int Find(int u){
        if(u==par[u]) return u;
        return par[u]=Find(par[u]);
    }
    void Union(int x, int y){
        x=Find(x), y=Find(y);
        if(x==y) return;
        cur-=val[x], cur-=val[y];
        if(x>y) swap(x,y);
        if(sz[x]>1) MIN[x][2]=min(MIN[x][2],a[y].val+a[y-1].val+a[y-2].val);
        if(sz[y]>1) MIN[x][2]=min(MIN[x][2],a[y].val+a[y+1].val+a[y-1].val);
        par[y]=x, sz[x]+=sz[y], sum[x]+=sum[y];
        for(int i = 0; i<3; ++i)
            MIN[x][i]=min(MIN[x][i],MIN[y][i]);
        if(sz[x]&1) val[x]=max(sum[x]-MIN[x][2],sum[x]-MIN[x][x&1]);
        else val[x]=sum[x];
        cur+=val[x];
    }
}dsu;
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
    rs.resize(sz(E));
    n=sz(W);
    for(int i = 1; i<=n; ++i)
        sum+=A[i-1], a[i].w=W[i-1], a[i].a=A[i-1], a[i].b=B[i-1], a[i].val=A[i-1]-B[i-1];
    for(int i = 0; i<sz(E); ++i)
        v.pb(E[i],mp(2,i));
    sort(a+1,a+n+1);
    for(int i = 2; i<=n; ++i){
        v.pb(a[i].w-a[i-1].w,mp(0,i));
        if(i<n) v.pb(a[i+1].w-a[i-1].w,mp(1,i));
    }
    sort(v.begin(),v.end());
    dsu.init(n);
    for(pair<int,pair<int,int>>& p : v){
        if(p.se.fi==0){
            int x=p.se.se;
            dsu.Union(x,x-1);
        }else if(p.se.fi==1){
            int x=dsu.Find(p.se.se),y=p.se.se;
            cur-=dsu.val[x], dsu.MIN[x][2]=min(dsu.MIN[x][2],a[y].val);
            dsu.val[x]=max(dsu.val[x],dsu.sum[x]-dsu.MIN[x][2]);
            cur+=dsu.val[x];
        }else rs[p.se.se]=sum-cur;
    }
    return rs;
}
//int main()
//{
//    tt;
//    if(fopen((NAME + ".INP").c_str(), "r")) fo;
//    int n,q;
//    cin >> n;
//    vector<int> w(n),a(n),b(n);
//    for(int i = 0; i<n; ++i)
//        cin >> w[i] >> a[i] >> b[i];
//    cin >> q;
//    vector<int> e(q);
//    for(int i = 0; i<q; ++i)
//        cin >> e[i];
//    vector<ll> rs=calculate_costs(w,a,b,e);
//    for(ll& x : rs) cout << x << "\n";
//}

• 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