Submission #588458

#	Time	Username	Problem	Language	Result	Execution time	Memory
588458		Piokemon	Potatoes and fertilizers (LMIO19_bulves)	C++17	0 / 100	14 ms	2072 KiB

bulves

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

int nawoz[500'009];
int ziem[500'009];
int lewo[500'009];
int prawo[500'009];
int ziem_sum[500'009];
constexpr int base = 524288;
int tree[base*2 + 9];

void add(int x, int val){
    x = base + x - 1;
    while(x>0){
        tree[x] += val;
        x = x/2;
    }
}

int query(int a, int b, int p, int k, int x){
    if (b<p || a>k){
        return 0;
    }
    if (p<=a && b<=k){
        return tree[x];
    }
    int mid = (a+b)/2;
    return query(a,mid,p,k,2*x) + query(mid+1,b,p,k,2*x+1);
}

int fintl(int a){
    if (lewo[a] == a){
        return a;
    }
    return lewo[a] = fintl(lewo[a]);
}

int fintr(int a){
    if (prawo[a] == a){
        return a;
    }
    return prawo[a] = fintr(prawo[a]);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,p1,p2,odp,temp;
    cin >> n;
    nawoz[0] = 0;
    lewo[0] = 0;
    nawoz[n+1] = 0;
    prawo[n+1] = n+1;
    for (int x=1;x<=n;x++){
        cin >> nawoz[x] >> ziem[x];
        temp = min(nawoz[x],ziem[x]);
        nawoz[x] -= temp;
        ziem[x] -= temp;
        add(x,nawoz[x]);
        if (nawoz[x] > 0){
            lewo[x] = x;
        }
        else{
            lewo[x] = lewo[x-1];
        }
    }
    ziem_sum[n+1] = 0;
    for (int x=n;x>=1;x--){
        ziem_sum[x] = ziem_sum[x+1] + ziem[x];
        if (nawoz[x] > 0){
            prawo[x] = x;
        }
        else{
            prawo[x] = prawo[x+1];
        }
    }
    odp = 0;
    for (int x=1;x<=n;x++){
        if (ziem[x] == 0){
            continue;
        }
        if (nawoz[x] == 0){
            lewo[x] = lewo[x-1];
            prawo[x] = prawo[x+1];
        }
        fintl(x);
        fintr(x);
        p1 = lewo[x];
        p2 = prawo[x];
        while(ziem[x] > 0){
            if (p1==0){
                temp = min(ziem[x],nawoz[p2]);
                ziem[x] -= temp;
                nawoz[p2] -= temp;
                add(p2,-temp);
                odp += abs(x-p2) * temp;
                if (nawoz[p2] == 0){
                    lewo[p2] = lewo[p2-1];
                    prawo[p2] = prawo[p2+1];
                }
                fintr(p2);
                p2 = prawo[p2];
            }
            else if (p2 == n+1 || query(1,base,p2,n,1) < ziem_sum[p2] + ziem[x]){
                temp = min(ziem[x],nawoz[p1]);
                ziem[x] -= temp;
                nawoz[p1] -= temp;
                add(p1,-temp);
                odp += abs(x-p1) * temp;
                if (nawoz[p1] == 0){
                    lewo[p1] = lewo[p1-1];
                    prawo[p1] = prawo[p1+1];
                }
                fintl(p1);
                p1 = lewo[p1];
            } 
            else if (abs(x-p1) > abs(x-p2)){
                temp = min(ziem[x],nawoz[p2]);
                ziem[x] -= temp;
                nawoz[p2] -= temp;
                add(p2,-temp);
                odp += abs(x-p2) * temp;
                if (nawoz[p2] == 0){
                    lewo[p2] = lewo[p2-1];
                    prawo[p2] = prawo[p2+1];
                }
                fintr(p2);
                p2 = prawo[p2];
            }
            else{
                temp = min(ziem[x],nawoz[p1]);
                ziem[x] -= temp;
                nawoz[p1] -= temp;
                add(p1,-temp);
                odp += abs(x-p1) * temp;
                if (nawoz[p1] == 0){
                    lewo[p1] = lewo[p1-1];
                    prawo[p1] = prawo[p1+1];
                }
                fintl(p1);
                p1 = lewo[p1];
            }
        }
    }
    cout << odp << "\n";
    return 0;
}

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