제출 #1124606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124606		Mike_Vu	Colouring a rectangle (eJOI19_colouring)	C++17	100 / 100	550 ms	21316 KiB

colouring

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define BITJ(x, j) (((x)>>(j))&1)
#define MASK(x) (1LL << (x))

template<typename T> bool maximize(T& x, const T& y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T& x, const T& y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

struct SMT{
    int trsz;
    vector<ll> tr, lazy;
    void init(int n) {
        trsz = 1;
        while (trsz < n) trsz <<= 1;
        tr.assign(trsz<<1, 0);
        lazy.assign(trsz<<1, 0);
    }
    void fix(int id) {
        if (lazy[id] == 0) return;
        if (id < trsz ){
            lazy[id<<1] += lazy[id];
            lazy[id<<1|1] += lazy[id];
        }
        tr[id] += lazy[id];
        lazy[id] = 0;
    }
    void update(int u, int v, int l, int r, int id, ll val) {
        fix(id);
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            lazy[id] += val;
            fix(id);
            return;
        }
        int mid = (l+r)>>1;
        update(u, v, l, mid, id<<1, val);
        update(u, v, mid+1, r, id<<1|1, val);
        tr[id] = min(tr[id<<1], tr[id<<1|1]);
    }
    void update(int u, int v, ll val) {
        update(u, v, 1, trsz, 1, val);
    }
    ll query(int u, int v, int l, int r, int id) {
        fix(id);
        if (l > v || r < u) return LLONG_MAX;
        if (l >= u && r <= v) {
            return tr[id];
        }
        int mid = (l+r)>>1;
        ll g1 = query(u, v, l, mid, id<<1);
        ll g2 = query(u, v, mid+1, r, id<<1|1);
        return min(g1, g2);
    }
    ll query(int u, int v) {
        return query(u, v, 1, trsz, 1);
    }
};

const int maxn = 2e5+5;
int n, m;

namespace full{
    struct inter{
        int l, r, c;
        inter(int _l, int _r, int _c) {
            l = _l;
            r = _r;
            c = _c;
        }
    };
    bool cmpin1(inter a, inter b) {
        return a.l < b.l;
    }
    bool cmpin2(const inter &a, const inter &b) {
        return a.r < b.r;
    }
    int val1[maxn], val2[maxn];
    vector<inter> in1, in2;
    ll ans = 0;
    ll ps[maxn];
    SMT tr;
    ll solvedp(int len, int val[], vector<inter> qu) {
        ps[0] = 0;
        tr.init(len);
        vector<inter> qu2;
        qu2 = qu;
        sort(ALL(qu), cmpin1);
        sort(ALL(qu2), cmpin2);
        for (int i= 1; i <= len; i++) {
            ps[i] = ps[i-1] + val[i];
        }
        auto sumps = [&](int l, int r) -> ll{
            if (l > r) return 0LL;
            return ps[r]-ps[l-1];
        };
        int j = 0, j2 = 0;
        ll suminter = 0, res = LLONG_MAX;
//        for (int i= 1; i <= len; i++) {
//            cout << val[i] << ' ';
//        }
//        cout << "\n";
//        for (inter e : qu2) {
//            cout << e.l << ' ' << e.r << ' ' << e.c << "\n";
//        }
        for (int i= 1; i <= len; i++) {
            //update intervals
            while (j < (int)qu.size() && qu[j].l == i) {
                int l = qu[j].l, c = qu[j].c;
                suminter += c;
                if (l > 1) tr.update(1, l-1, c);
                ++j;
            }
            while (j2 < (int)qu2.size() && qu2[j2].r < i) {
                int l = qu2[j2].l, c = qu2[j2].c;
                suminter -= c;
                if (l > 1) tr.update(1, l-1, -c);
                ++j2;
            }
            //case first
            ll dp = suminter+sumps(1, i-1);
            //case SMT
            if (i > 1) minimize(dp, tr.query(1, i-1));
            minimize(res, dp+sumps(i+1, len));
//            cout << i << ' ' << dp << ' ' << suminter << ' ' << sumps(1, i-1) << ' ';
//            if (i > 1) cout << tr.query(1, i-1);
//            cout << "\n";
            //update SMT(dp + val)
            tr.update(i, i, dp);
            if (i > 1) tr.update(1, i-1, val[i]);
        }
        return min(res, sumps(1, len));
    }
    void solve() {
        //input -> two arrays
        for (int i = 1; i <= m+n-1; i++) {
            int c;
            cin >> c;
            int l, r;
            if (i > m) l = 1+i-m;
            else l = m-i+1;
            if (i > n) r = n+m-1-(i-n);
            else r = m+i-1;
            if ((m&1) == (i&1)) in1.pb(inter((l+1)/2, (r+1)/2, c));
            else in2.pb(inter((l+1)/2, (r+1)/2, c));
        }
        for (int i = 1; i <= m+n-1; i++) {
            int c;
            cin >> c;
            if (i&1) val1[(i+1)/2] = c;
            else val2[(i+1)/2] = c;
        }
        ans += solvedp((m+n)/2, val1, in1);
//        cout << "ans " << ans << "\n";
        ans += solvedp((m+n-1)/2, val2, in2);
//        cout << "\n";
        cout << ans;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> n >> m;
    return full::solve(), 0;
}
/*
3 2
3 4 1 1
4 1 2 2
7

3 2
4 2 2 1
1 4 4 1
*/

• 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