Submission #588421

#	Time	Username	Problem	Language	Result	Execution time	Memory
588421		Piokemon	Potatoes and fertilizers (LMIO19_bulves)	C++17	0 / 100	1 ms	340 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 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];
        if (nawoz[x] > 0){
            lewo[x] = x;
        }
        else{
            lewo[x] = lewo[x-1];
        }
    }
    for (int x=n;x>=1;x--){
        if (nawoz[x] > 0){
            prawo[x] = x;
        }
        else{
            prawo[x] = prawo[x+1];
        }
    }
    odp = 0;
    for (int x=1;x<=n;x++){
        temp = min(ziem[x],nawoz[x]);
        ziem[x] -= temp;
        nawoz[x] -= temp;
        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;
                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){
                temp = min(ziem[x],nawoz[p1]);
                ziem[x] -= temp;
                nawoz[p1] -= temp;
                odp += abs(x-p1) * temp;
                if (nawoz[p1] == 0){
                    lewo[p1] = lewo[p1-1];
                    prawo[p1] = prawo[p1+1];
                }
                fintr(p1);
                p1 = lewo[p1];
            } 
            else if (abs(x-p1) >= abs(x-p2)){
                temp = min(ziem[x],nawoz[p2]);
                ziem[x] -= temp;
                nawoz[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;
                odp += abs(x-p1) * temp;
                if (nawoz[p1] == 0){
                    lewo[p1] = lewo[p1-1];
                    prawo[p1] = prawo[p1+1];
                }
                fintr(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