Submission #1020239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020239		esomer	Colouring a rectangle (eJOI19_colouring)	C++17	20 / 100	260 ms	25772 KiB

colouring

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 10
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20