oj.uz

답안 #1020239

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1020239 2024-07-11T18:03:32 Z esomer Colouring a rectangle (eJOI19_colouring) C++17
20 / 100
 260 ms 25772 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.
        ll cost1 = up[col1];
        sum += cost1; //Sumo el cost de les dues graelles a columna 0 i fila n-1 que ja no cobreixo.
        int c1;
        if(col1 >= m){
            // cout << "here1" << endl;
            c1 = m-1 - (col1 - (m-1));
        }else c1 = col1;
        //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.
        st.set(0, c1, -cost1); //No inclou c1, perquè és obert en r.
        
        //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; 
        if(!(y >= m || col2 == col1)){
            //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 cost2 = up[col2];
            sum += cost2; 
            
            int c2;
            if(col2 >= m){
                // cout << "here2" << endl;
                c2 = m-1 - (col2 - (m-1));
            }else c2 = col2;
            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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 10.0

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

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 238 ms 25772 KB Output is correct
2 Correct 241 ms 25340 KB Output is correct
3 Correct 233 ms 25244 KB Output is correct
4 Correct 240 ms 25700 KB Output is correct
5 Correct 237 ms 25492 KB Output is correct
6 Correct 246 ms 23944 KB Output is correct
7 Correct 260 ms 24980 KB Output is correct

Subtask #7
0 / 20.0

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