Submission #457994

#	Time	Username	Problem	Language	Result	Execution time	Memory
457994		SamAnd	Colouring a rectangle (eJOI19_colouring)	C++17	100 / 100	941 ms	46912 KiB

colouring

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 400005;
const ll INF = 1000000009000000009;

ll minu[N * 4];
ll laz[N * 4];

void clr(int tl, int tr, int pos)
{
    minu[pos] = laz[pos] = 0;
    if (tl == tr)
        return;
    int m = (tl + tr) / 2;
    clr(tl, m, pos * 2);
    clr(m + 1, tr, pos * 2 + 1);
}

void shi(int pos)
{
    if (laz[pos] == 0)
        return;
    minu[pos * 2] += laz[pos];
    laz[pos * 2] += laz[pos];
    minu[pos * 2 + 1] += laz[pos];
    laz[pos * 2 + 1] += laz[pos];
    laz[pos] = 0;
}

void ubd(int tl, int tr, int l, int r, ll y, int pos)
{
    if (l > r)
        return;
    if (tl == l && tr == r)
    {
        minu[pos] += y;
        laz[pos] += y;
        return;
    }
    shi(pos);
    int m = (tl + tr) / 2;
    ubd(tl, m, l, min(m, r), y, pos * 2);
    ubd(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1);
    minu[pos] = min(minu[pos * 2], minu[pos * 2 + 1]);
}

ll qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return INF;
    if (tl == l && tr == r)
        return minu[pos];
    shi(pos);
    int m = (tl + tr) / 2;
    return min(qry(tl, m, l, min(m, r), pos * 2),
               qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

vector<int> v[N];
ll dp[N];

ll solvv(vector<int> a, vector<pair<pair<int, int>, int> > b)
{
    int n = sz(a) - 1;
    for (int i = 0; i <= n + 1; ++i)
    {
        v[i].clear();
        dp[i] = 0;
    }
    clr(0, n, 1);

    for (int i = 1; i < sz(b); ++i)
    {
        v[b[i].fi.fi].push_back(i);
        v[b[i].fi.se + 1].push_back(-i);
    }

    ll s = 0;
    for (int i = 1; i <= n + 1; ++i)
    {
        for (int j = 0; j < v[i].size(); ++j)
        {
            if (v[i][j] > 0)
            {
                ubd(0, n, b[v[i][j]].fi.fi, b[v[i][j]].fi.se, -b[v[i][j]].se, 1);
                s += b[v[i][j]].se;
            }
            else
            {
                ubd(0, n, b[-v[i][j]].fi.fi, b[-v[i][j]].fi.se, b[-v[i][j]].se, 1);
                s -= b[-v[i][j]].se;
            }
        }
        if (i == n + 1)
            break;
        dp[i] = s + qry(0, n, 0, i - 1, 1);
        ubd(0, n, 0, i - 1, a[i], 1);
        ubd(0, n, i, i, dp[i], 1);
    }

    return minu[1];
}

void solv()
{
    int n, m;
    int* a, *b;

    int* l, *r;

    cin >> n >> m;

    a = new int[n + m + 5];
    b = new int[n + m + 5];
    l = new int[n + m + 5];
    r = new int[n + m + 5];

    for (int i = 1; i <= n + m - 1; ++i)
        cin >> a[i];
    for (int i = 1; i <= n + m - 1; ++i)
        cin >> b[i];

    for (int i = 1; i <= n + m - 1; ++i)
    {
        int x, y;
        if (i <= m)
        {
            x = 1;
            y = (m - i + 1);
        }
        else
        {
            x = (i - m + 1);
            y = 1;
        }

        int q = min(n - x + 1, m - y + 1);

        int u = min(x - 1, m - y);

        int xx = x - u;
        int yy = y + u;

        int L, R;

        if (xx == 1)
        {
            L = yy;
        }
        else
        {
            L = m + xx - 1;
        }

        R = L + q * 2 - 1 - 1;

        //cout << i << ' ' << L << ' ' << R << "\n";
        l[i] = L;
        r[i] = R;
    }

    ll ans = 0;

    vector<int> v;
    v.push_back(-1);
    for (int i = 1; i <= n + m - 1; ++i)
    {
        if (i % 2 == l[1] % 2)
        {
            v.push_back(b[i]);
        }
    }
    vector<pair<pair<int, int>, int> > vv;
    vv.push_back(m_p(m_p(-1, -1), -1));
    for (int i = 1; i <= n + m - 1; i += 2)
    {
        vv.push_back(m_p(m_p(l[i] / 2 + l[i] % 2, r[i] / 2 + r[i] % 2), a[i]));
    }

    ans += solvv(v, vv);

    v.clear();
    v.push_back(-1);
    for (int i = 1; i <= n + m - 1; ++i)
    {
        if (i % 2 == l[2] % 2)
        {
            v.push_back(b[i]);
        }
    }
    vv.clear();
    vv.push_back(m_p(m_p(-1, -1), -1));
    for (int i = 2; i <= n + m - 1; i += 2)
    {
        vv.push_back(m_p(m_p(l[i] / 2 + l[i] % 2, r[i] / 2 + r[i] % 2), a[i]));
    }

    ans += solvv(v, vv);

    cout << ans << "\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Compilation message (stderr)

colouring.cpp: In function 'll solvv(std::vector<int>, std::vector<std::pair<std::pair<int, int>, int> >)':
colouring.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int j = 0; j < v[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~

• 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