Submission #1239911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239911		_ll	Colouring a rectangle (eJOI19_colouring)	C++20	100 / 100	642 ms	41612 KiB

colouring

#include<bits/stdc++.h> // recorrencia tenho que achar o menor custo pronto até j e ligar todos d baixo
using namespace std; // a partir de j, preciso desligar os d cima onde as diagonais d baixo estao ligadas
typedef long long ll; // agora só pegar o minimo de todos os js, lembrando que tenho q andar uma vez a mais

void prop(vector<array<ll, 2>> &ls, ll at, ll atl, ll atr){ // pra poder olhar só para respostas anteriores 
    if(!ls[at][0]) return;                                  // (pra usar a invariante ao final)
    ls[at][1] += ls[at][0];
    if(atl != atr)
        ls[2 * at][0] += ls[at][0], ls[2 * at + 1][0] += ls[at][0];
    ls[at][0] = 0;
}

void up(vector<array<ll, 2>> &ls, ll at, ll atl, ll atr, ll lq, ll rq, ll vl){
    prop(ls, at, atl, atr);
    if(rq < atl || atr < lq) return;
    if(lq <= atl && atr <= rq){
        ls[at][0] = vl;
        prop(ls, at, atl, atr);
        return;
    }
    ll m = (atl + atr) / 2;
    up(ls, 2 * at, atl, m, lq, rq, vl), up(ls, 2 * at + 1, m + 1, atr, lq, rq, vl);
    ls[at][1] = min(ls[2 * at][1], ls[2 * at + 1][1]);
}

ll qr(vector<array<ll, 2>> &ls, ll at, ll atl, ll atr, ll lq, ll rq){
    prop(ls, at, atl, atr);
    if(rq < atl || atr < lq)        return 1e16;
    if(lq <= atl && atr <= rq)      return ls[at][1];
    ll m = (atl + atr) / 2, r1 = qr(ls, 2 * at, atl, m, lq, rq);
    return min(r1, qr(ls, 2 * at + 1, m + 1, atr, lq, rq));
}

ll sol(vector<ll> &a, vector<array<ll, 3>> &b){
    ll sz = a.size() + 1;
    vector<ll> dp(sz); // seg com lazy
    vector<vector<array<ll, 2>>> sl(sz + 1); // 1 indexado e um espaco a mais pra não dar segfal
    vector<array<ll, 2>> ls(4 * sz, {0, 0}); // lazy e seg
    for(ll i = 0; i < b.size(); i++) // pro sweep line (inicio, fim)
        sl[b[i][0]].push_back({-1, i}), sl[b[i][1] + 1].push_back({1, i}); 
    ll s = 0;
    for(ll i = 1; 1; i++){
        for(auto [j, k] : sl[i]){ // tenho que rodar uma iteração a mais no inicio
            up(ls, 1, 0, sz, b[k][0], b[k][1], j * b[k][2]); // pra considerar
            s -= j * b[k][2]; // sem ativar nenhum na diagonal a 
        }
        if(i == sz - 1) return qr(ls, 1, 0, sz, 0, sz - 2); // cuidado com o sz - 2
        ll vl = qr(ls, 1, 0, sz, 0, i - 1);
        dp[i] = s + vl;
        up(ls, 1, 0, sz, 0, i - 1, a[i]); // pra todo j menor eu deixo o ai ligado
        up(ls, 1, 0, sz, i, i, dp[i]);   // afina
    }
    return 0;
}

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

    ll n, m; cin >> n >> m;
    vector<array<ll, 3>> b, p; 
    vector<ll> b2 = {-1}, p2 = b2;
    for(ll i = 1, vl, l = m, r = m, dl = -1, dr = 1; i <= n + m - 1; i++, l += dl, r += dr){
        cin >> vl;
        if(i % 2)  b.push_back({(l + 1) / 2, (r + 1) / 2, vl});
        else       p.push_back({(l + 1) / 2, (r + 1) / 2, vl});
        if(l == 1)          dl = 1;
        if(r == n + m - 1) dr = -1;
    }
    for(ll i = 1, vl; i <= n + m - 1; i++){
        cin >> vl;
        if(i % 2 == m % 2) b2.push_back(vl);
        else               p2.push_back(vl);
    }
    cout << sol(b2, b) + sol(p2, p) << "\n"; // esboco, termino amanha ta muito errado
} 

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20