oj.uz

답안 #1020233

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1020233 2024-07-11T17:51:34 Z esomer Colouring a rectangle (eJOI19_colouring) C++17
20 / 100
 240 ms 21188 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e18;

struct segTree{
    vector<ll> v, upd;
    int sz;
    void init(int n){
        sz = 1;
        while(sz < n) sz *= 2;
        v.assign(2 * sz, INF);
        upd.assign(2 * sz, 0);
    }
    void set(int l, int r, ll val, int x, int lx, int rx){
        if(lx >= l && rx <= r){
            upd[x] += val;
            v[x] += val;
            return;
        }else if(lx >= r || rx <= l) return;
        int m = (lx + rx) / 2;
        set(l, r, val, 2 * x + 1, lx, m);
        set(l, r, val, 2 * x + 2, m, rx);
        v[x] = min(v[2 * x + 1], v[2 * x + 2]) + upd[x];
    }
    void set(int l, int r, ll val){
        set(l, r, val, 0, 0, sz);
    }
    ll calc(int l, int r, int x, int lx, int rx){
        if(lx >= l && rx <= r) return v[x];
        else if(lx >= r || rx <= l) return 1e18;
        int m = (lx + rx) / 2;
        ll c1 = calc(l, r, 2 * x + 1, lx, m);
        ll c2 = calc(l, r, 2 * x + 2, m, rx);
        return min(c1, c2) + upd[x];
    }
    ll calc(int l, int r){
        return calc(l, r, 0, 0, sz);
    }
};

ll getSum(int l, int r, vector<ll>& pre){
    if(l > r) return 0;
    if(l > 0) return pre[r] - pre[l-1];
    else return pre[r];
}

ll solve(int n, int m, vector<int>& down, vector<int>& up){
    // cout << "Down:\n";
    // for(int x : down) cout << x << " "; 
    // cout << "\n";
    // cout << "Up:\n";
    // for(int x : up) cout << x << " "; 
    // cout << "\n";
    segTree st; st.init(m);
    vector<ll> pre(n+m-1);
    pre[0] = up[0];
    for(int i = 1; i < n+m-1; i++){
        pre[i] = pre[i-1] + up[i];
        //Em guardo el prefix dels costs dels ups, per poder calcular quant he de pagar
        //per cada down.
    }
    ll sum = 0;
    for(int i = m-1; i >= 0; i--){
        //Itero sobre els downs, i miro quant he de pagar aquest és l'últim que coloco.
        sum += down[i];
        int s1 = m-i-1 + 1;
        int s2 = m-i-1 + (m-1 - (m-1-i)) * 2 - 1;
        s2 = min(s2, n+m-2);
        st.set(m-1-i, m-i, -INF);
        if(i == 0) st.set(m-1-i, m-i, sum); //No hi ha rang d'up entre mig si ja estic a la cantonada.
        else st.set(m-1-i, m-i, sum + getSum(s1, s2, pre)); //Considero el rang d'ups que he de pagar.
        // cout << "s1 " << s1 << " s2 " << s2 << " sum " << sum << " getSum " << getSum(s1, s2, pre) << "\n";
        // cout << "i " << i << " col " << m-1-i << " " << m - i << " calc "<< st.calc(m-1-i, m-i) << "\n";
    }
    sum = 0;
    for(int i = m; i < n+m-1; i++){
        //Ara considero les down de la meitat inferior de la graella. Inicialment
        //coloco totes i després trec poc a poc i calculo la resposta en cada moment.
        sum += down[i];
    }
    // cout << pre.back() << " sum " << sum << " st.v[0] "<< st.v[0] << "\n";
    ll ans = min(pre.back(), sum + st.v[0]);
    //Casos inicials: totes son ups o coloco totes les down de la meitat inferior i el millor de la 
    //meitat superior.
    //A partir d'ara, com no totes són ups, la diagonal cap abaix que surt de (0, 0) sempre està
    //inclosa.
    for(int i = n+m-2; i >= m; i--){
        //Vaig eliminant downs des de la casella inferior esquerra fins a la que surt de 
        //(0, 0) (que mai l'arribaré a eliminar).
        sum -= down[i]; //Resto aquest cost.
        //Quan faig up, es conserva la suma. Per tant, jo vull veure a quina cel·la de la forma
        //(0, x) correspon (y, 0). -> x = y.
        int col1 = i-m+1; //Perquè la row és i-m+1.
        
        //Quan faig up, es conserva la suma. Per tant, jo vull veure a quina cel·la de la forma
        //(0, x) correspon (n-1, y). -> x = y+n-1.
        int y = n+m-2-i;
        int col2 = y+n-1; 

        //Si col >= m, realment no estaràn a la fila 0, sino a la columna m-1, però em serveix
        //igual per saber l'índex de l'up.
        ll cost1 = up[col1];
        ll cost2 = up[col2];
        if(col1 == col2) cost2 = 0; //La cantonada la contava dos cops.
        sum += cost1 + cost2; //Sumo el cost de les dues graelles a columna 0 i fila n-1 que ja no cobreixo.
        
        //Ara al segment tree, he de descomptar als que inclouen aquests ups en la seva suma.
        //Vull veure quina és la cel·la de la fila 0 amb la que comparteixen down.
        int c1, c2;
        if(col1 >= m){
            // cout << "here1" << endl;
            c1 = m-1 - (col1 - (m-1));
        }else c1 = col1;
        if(col2 >= m){
            // cout << "here2" << endl;
            c2 = m-1 - (col2 - (m-1));
        }else c2 = col2;
        st.set(0, c1, -cost1); //No inclou c1, perquè és obert en r.
        st.set(0, c2, -cost2);
        // cout << "i " << i << " c1 " << c1 << " c2 " << c2 << " col1 " << col1 << " col2 " << col2 << " sum " << sum << " v[0] " << st.v[0] << "\n";
        // cout << "Fila baix col "<< y << " col0 row " << i-m+1 << "\n";
        ans = min(ans, sum + st.v[0]);
    }
    // cout << "Ans " << ans << "\n";
    return ans;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);

    /*
    Detall que no havia considerat. Realment, quan deixo de posar una down, i omplo amb ups, no estic
    omplint totes les caselles, només les de mateixa paritat, és una mica liada. Però, com les diagonals
    només cobreixen caselles de mateixa paritat, realment no és un problema, perquè vol dir que colorejar
    les caselles parelles i imparelles són dos problemes independents i puc fer el que tenia dos cops.*/

    int n, m; cin >> n >> m;
    vector<int> down(n+m-1);
    for(auto &i : down) cin >> i;
    vector<int> up(n+m-1);
    for(auto &i : up) cin >> i;
    vector<int> downOdd(n+m-1, 0), downEven(n+m-1, 0);
    int odd = (m-1)%2;;
    for(int i = 0; i < n + m - 1; i++){
        if(odd) downOdd[i] = down[i];
        else downEven[i] = down[i];
        odd ^= 1;
    }
    vector<int> upOdd(n+m-1, 0), upEven(n+m-1, 0);
    for(int i = 0; i < n + m - 1; i++){
        if(i%2) upOdd[i] = up[i];
        else upEven[i] = up[i];
    }
    ll ans = solve(n, m, downOdd, upOdd) + solve(n, m, downEven, upEven);
    cout << ans << "\n";
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 126 ms 14940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 21076 KB Output is correct
2 Correct 229 ms 21188 KB Output is correct
3 Correct 240 ms 21072 KB Output is correct
4 Correct 230 ms 21072 KB Output is correct
5 Correct 236 ms 21076 KB Output is correct
6 Correct 238 ms 21156 KB Output is correct
7 Correct 234 ms 21164 KB Output is correct

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -