제출 #1239418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239418		_ll	Colouring a rectangle (eJOI19_colouring)	C++20	0 / 100	722 ms	54024 KiB

colouring

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void prop(vector<array<ll, 2>> &ls, ll at, ll atl, ll atr){
    if(!ls[at][0]) return;
    ls[at][1] += ls[at][0] * (atr - atl + 1);
    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});
    for(ll i = 0; i < sz - 2; i++){ // pro sweep line
        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]){
            up(ls, 1, 0, sz, b[k][0], b[k][1], j * b[k][2]);
            s -= j * b[k][2];
        }
        if(i == sz - 1) break;
        ll vl = qr(ls, 1, 0, sz, 0, i - 1);
        dp[i] = s + vl;
        up(ls, 1, 0, sz, 0, i - 1, a[i]); // aviso pro proximo que posso não ligar nenhum
        up(ls, 1, 0, sz, i, i, dp[i]);
    }
    ll re = 1e16;
    for(ll i = 0; i < sz - 1; i++)
        re = min(re, qr(ls, 1, 0, sz, i, i));
    return re;
}

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