oj.uz

Submission #588440

# Submission time Handle Problem Language Result Execution time Memory
588440 2022-07-03T09:37:12 Z Piokemon Potatoes and fertilizers (LMIO19_bulves) C++17
0 / 100
 1 ms 340 KB 
#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];
        temp = min(nawoz[x],ziem[x]);
        nawoz[x] -= temp;
        ziem[x] -= temp;
        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++){
        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];
                }
                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;
                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];
                }
                fintl(p1);
                p1 = lewo[p1];
            }
        }
    }
    cout << odp << "\n";
    return 0;
}

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -