Submission #1166685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166685		akim9905	Nile (IOI24_nile)	C++20	38 / 100	99 ms	22324 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"
using namespace std;

#define fileio() freopen("input.txt","r",stdin); freopen("output.txt","w",stdout)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define cmprs(x) sort(all(x)),x.erase(unique(all(x)),x.end())
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)(a.size())

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int dx[] = {1,-1,0,0,1,1,-1,-1};
const int dy[] = {0,0,1,-1,1,-1,1,-1};
const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAX = 101010;

ll bsum[MAX];
ll ans=0;

struct segtr{
    //0-indexed!
    vector<ll> tr;
    int n;
    void rst(int sz) {
        n=sz;
        tr.resize((n+1)<<1,LINF);
    }

    void upd(int i, ll v) {
        tr[i+n] = min(tr[i+n], v); i+=n; //AWARE OF UPD POLICY!!
        for (i>>=1; i; i>>=1) tr[i] = min(tr[i<<1], tr[i<<1|1]);
    }

    ll qry(int l, int r) {
        ll ret = LINF;
        for (l+=n, r+=n; l<=r; l>>=1, r>>=1) {
            if (l&1) ret = min(ret, tr[l++]);
            if (~r&1) ret = min(ret, tr[r--]);
        }
        return ret;
    }
} seg1[2],seg2[2];


struct dsu {
    int n;
    vector<int> p,s;
    vector<pii> rng;
    vector<ll> v;

    void rst(int _n) {
        n=_n+10;
        p.resize(n);
        v.resize(n);
        s.resize(n,1);
        rng.resize(n);
        iota(all(p),0);
        for (int i=0; i<n; i++) rng[i]={i,i};
    }

    int fd(int a) {
        if (a==p[a]) return a;
        return p[a]=fd(p[a]);
    }

    int mg(int a, int b) {
        a=fd(a), b=fd(b);
        if (a==b) return 0;

        auto [l1,r1]=rng[a]; auto [l2,r2]=rng[b];
        int l3=min(l1,l2),r3=max(r1,r2);

        ll val=0;
        if ((s[a]+s[b])%2==0) {
            ans-=(v[a]+v[b]);
            ans+=bsum[r3]-bsum[l3-1];
            val=bsum[r3]-bsum[l3-1];
        }
        else {
            val=v[a]+v[b];
            ans-=(v[a]+v[b]);
            
            val=min(val,seg1[l3%2].qry(l3,r3)+bsum[r3]-bsum[l3-1]);
            val=min(val,seg2[l3%2].qry(l3,r3)+bsum[r3]-bsum[l3-1]);

            ans+=val;
        }

        p[b]=a;
        s[a]+=s[b], s[b]=0;
        rng[a]={l3,r3}, rng[b]={-1,0};
        v[a]=val;

        return 1;
    }
} uf;

typedef array<ll,3> arr;

int n,q;
arr a[MAX];
pll qry[MAX];

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    n=sz(W),q=sz(E);
    for (int i=1; i<=n; i++) a[i][0]=W[i-1];
    for (int i=1; i<=n; i++) a[i][1]=A[i-1];
    for (int i=1; i<=n; i++) a[i][2]=B[i-1];

    vector<ll> ret(q);
    sort(a+1,a+n+1);

    for (int i=0; i<q; i++) qry[i]={E[i],i};
    sort(qry,qry+q);

    priority_queue<pll,vector<pll>,greater<pll>> pq1,pq2;
    for (int i=1; i+1<=n; i++) pq1.push({a[i+1][0]-a[i][0],i});
    for (int i=1; i+2<=n; i++) pq2.push({a[i+2][0]-a[i][0],i});

    seg1[0].rst(MAX),seg1[1].rst(MAX);
    seg2[0].rst(MAX),seg2[1].rst(MAX);
    uf.rst(MAX);

    for (int i=1; i<=n; i++) {
        uf.v[i]=a[i][1];
        ans+=a[i][1];
        bsum[i]=bsum[i-1]+a[i][2];
    }
    
    for (int i=0; i<q; i++) {
        auto [d,qi]=qry[i];

        vector<pii> idx;
        while (!pq1.empty() && pq1.top().first<=d) {
            auto [dif,i1]=pq1.top(); pq1.pop(); int i2=i1+1;
            seg1[i1%2].upd(i1,a[i1][1]-a[i1][2]);
            seg1[i2%2].upd(i2,a[i2][1]-a[i2][2]);
            idx.pb({i1,i2});
        }

        while (!pq2.empty() && pq2.top().first<=d) {
            auto [dif,i1]=pq2.top(); pq2.pop();
            seg2[i1%2].upd(i1+1,a[i1+1][1]-a[i1+1][2]);
        }

        for (auto [i1,i2]:idx) uf.mg(i1,i2);
        
        ret[qi]=ans;
    }
    
    return ret;
}

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