Submission #1247230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247230		andrei_n	Colouring a rectangle (eJOI19_colouring)	C++20	100 / 100	344 ms	44804 KiB

colouring

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.h>
#else
#define debug
#endif // LOCAL
#define int long long

using namespace std;

struct Range
{
    int l, r, c;
};

const int INF = 9999999999999999LL;
int dp[800005];
bool lazy[800005];
int best[200005];
int aintSize;

void _update(int st, int dr, int pos, int a, int b, int x)
{
    if(a <= st && dr <= b)
    {
        dp[pos] += x;
        lazy[pos] = 1;
    }
    else
    {
        int mij = (st+dr>>1);
        if(lazy[pos])
        {
            lazy[pos] = 0;
            lazy[pos<<1] = lazy[pos<<1|1] = 1;
            int by = dp[pos] - min(dp[pos<<1], dp[pos<<1|1]);
            dp[pos<<1] += by;
            dp[pos<<1|1] += by;
        }
        if(a <= mij) _update(st, mij, pos<<1, a, b, x);
        if(b > mij) _update(mij+1, dr, pos<<1|1, a, b, x);
        dp[pos] = min(dp[pos<<1], dp[pos<<1|1]);
    }
}

void _query(int st, int dr, int pos, int a, int b, int &res)
{
    if(a <= st && dr <= b)
        res = min(res, dp[pos]);
    else
    {
        int mij = (st+dr>>1);
        if(lazy[pos])
        {
            lazy[pos] = 0;
            lazy[pos<<1] = lazy[pos<<1|1] = 1;
            int by = dp[pos] - min(dp[pos<<1], dp[pos<<1|1]);
            dp[pos<<1] += by;
            dp[pos<<1|1] += by;
        }
        if(a <= mij) _query(st, mij, pos<<1, a, b, res);
        if(b > mij) _query(mij+1, dr, pos<<1|1, a, b, res);
    }
}

void add(int l, int r, int x)
{
    _update(0, aintSize, 1, l, r, x);
}

int mini(int l, int r)
{
    int res = INF;
    _query(0, aintSize, 1, l, r, res);
    return res;
}

int solve(int *a, int *b, int *l, int *r, int n, int m)
{
    aintSize = m;
    debug("solve(n = %, m = %)\n", n, m);
    for(int i=1; i<=n; ++i)
        debug("a[%] = %, l[%] = %, r[%] = %\n", i, a[i], i, l[i], i, r[i]);
    for(int i=1; i<=m; ++i)
        debug("b[%] = %\n", i, b[i]);
    vector<Range> v;
    for(int i=1; i<=n; ++i)
        v.push_back({l[i], r[i], a[i]});
    sort(v.begin(), v.end(), [](const Range &x, const Range &y){return x.l < y.l;});
    vector<vector<Range>> what(m+1);
    for(auto &i : v)
        what[i.r].push_back(i);
    vector<vector<int>> sum(m+1);
    for(int i=1; i<=m; ++i)
    {
        if(what[i].empty()) continue;
        sum[i].assign(what[i].size(), 0);
        sum[i][0] = what[i][0].c;
        for(int j=1; j<what[i].size(); ++j)
            sum[i][j] = sum[i][j-1] + what[i][j].c;
        for(int j=0; j<sum[i].size(); ++j)
            debug("sum[%][%] = %\n", i, j, sum[i][j]);
    }
    debug("ok\n");
    for(int i=1; i<=4*m; ++i)
        dp[i] = INF;
    add(0, 0, -INF);
    best[0] = 0;
    for(int i=1; i<=m; ++i)
    {
        best[i] = INF;
        add(0, i-1, b[i]);
        add(i, i, best[i-1] - INF);
        for(auto &j : what[i])
            add(j.l, i, j.c);
        best[i] = mini(0, i);
//        for(int j=0; j<=i; ++j)
//        {
//            if(i != j)
//            {
//                dp[i][j] = dp[i-1][j] + b[i];
//                auto it = lower_bound(what[i].begin(), what[i].end(), Range({j+1, i, 0}), [](const Range &x, const Range &y){return x.l < y.l;});
//                int nr = it - what[i].begin();
//                if(--nr >= 0)
//                    dp[i][j] += sum[i][nr];
//            }
//            else
//            {
//                dp[i][j] = best[i-1] + (sum[i].empty() ? 0 : sum[i].back());
//            }
//            best[i] = min(best[i], dp[i][j]);
//            debug("dp[%][%] = %\n", i, j, dp[i][j]);
//        }
    }
    return best[m];
}

int m, n;
int a[2][200005], b[2][200005];
int l[2][200005], r[2][200005];

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>m>>n;
    for(int i=1; i<=m+n-1; ++i)
        cin>>a[i&1][i+1>>1];
    for(int i=1; i<=m+n-1; ++i)
        cin>>b[i&1][i+1>>1];
    int sz[2] = {};
    for(int i=1; i<=m+n-1; ++i)
    {
        int fl, fc;
        if(i <= n)
        {
            fl = 1;
            fc = n - i + 1;
        }
        else
        {
            fl = i - n + 1;
            fc = 1;
        }
        l[i&1][i+1>>1] = fc + fl - 1;
        int oth = min(i, m);
        r[i&1][i+1>>1] = l[i&1][i+1>>1] + (oth - fl) * 2;
        l[i&1][i+1>>1] = (l[i&1][i+1>>1]+1>>1);
        r[i&1][i+1>>1] = (r[i&1][i+1>>1]+1>>1);
        sz[i&1] = (i+1>>1);
    }
    if(n & 1)
        cout<<solve(a[0], b[0], l[0], r[0], sz[0], sz[0]) + solve(a[1], b[1], l[1], r[1], sz[1], sz[1]);
    else
        cout<<solve(a[0], b[1], l[0], r[0], sz[0], sz[1]) + solve(a[1], b[0], l[1], r[1], sz[1], sz[0]);
    return 0;
}

• 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