Submission #1284422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284422		imarn	Potatoes and fertilizers (LMIO19_bulves)	C++20	30 / 100	53 ms	34108 KiB

bulves

//#include "festival.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define sz(x) (ll)x.size()
#define cd complex<double>
#define t3 tuple<ll,ll,ll>
using namespace std;
const int mxn=2e5+5;
priority_queue<pll>pq[mxn];
vector<pii>g[mxn];
ll cv[mxn]{0},x[mxn],y[mxn],d[mxn],rs=0;
void dfs(int u,int p){
    d[u]=x[u]-y[u];
    for(auto [v,w]:g[u]){
        if(v==p)continue;
        dfs(v,u);
        cv[v]=w;d[u]+=d[v];
    }
}
void solve(int u,int p){
    for(auto [v,w]:g[u]){
        if(v==p)continue;
        solve(v,u);
        if(pq[v].size()>pq[u].size())swap(pq[u],pq[v]);
        while(!pq[v].empty())pq[u].push(pq[v].top()),pq[v].pop();
    }
    if(d[u]<0){
        rs-=d[u]*cv[u];d[u]=0;
    }rs+=d[u]*cv[u];
    ll cur=cv[u];
    while(!pq[u].empty()&&cur>0&&pq[u].top().f>=d[u]){
        auto [a,b]=pq[u].top();pq[u].pop();
        int tt=min(cur,b);
        b-=tt;cur-=tt;
        if(b!=0)pq[u].push({a,b});
    }pq[u].push({d[u],2*cv[u]-cur});
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=0;i<n-1;i++){
        g[i+1].pb({i+2,1});
        g[i+2].pb({i+1,1});
    }for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    int rt=1;dfs(rt,rt);solve(rt,rt);
    while(!pq[rt].empty()){
        rs-=min(pq[rt].top().f,d[rt])*pq[rt].top().s;pq[rt].pop();
    }cout<<rs;
}

• Subtask 1: 0 / 24
• Subtask 2: 0 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 0 / 36