Submission #1225520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225520		badge881	Colouring a rectangle (eJOI19_colouring)	C++20	100 / 100	320 ms	23496 KiB

colouring

#include <bits/stdc++.h>

using namespace std;

const int kN = 2e5;
const long long INF = 2e18L;
int a[2 * kN], v[1 + kN];
tuple<int, int, int> intervals[2 * kN];
vector<pair<int, int>> rEnd[1 + kN];

void minSelf(long long &x, long long y)
{
    if (y < x)
        x = y;
}

struct SegTree
{
    int n;
    vector<long long> t, lazy;

    SegTree(int N) : n(N)
    {
        int dim = 1;
        while (dim < n + 1)
            dim *= 2;
        dim *= 2;
        t.resize(dim);
        lazy.resize(dim);
    }

    void push(int x)
    {
        if (lazy[x] == 0)
            return;
        for (int y = 2 * x; y <= 2 * x + 1; ++y)
        {
            t[y] += lazy[x];
            lazy[y] += lazy[x];
        }
        lazy[x] = 0;
    }

    void rangeAdd(int x, int lx, int rx, int st, int dr, long long v)
    {
        if (st <= lx && rx <= dr)
        {
            t[x] += v;
            lazy[x] += v;
            return;
        }
        push(x);
        int mid = (lx + rx) / 2;
        if (st <= mid)
            rangeAdd(x * 2, lx, mid, st, dr, v);
        if (mid < dr)
            rangeAdd(x * 2 + 1, mid + 1, rx, st, dr, v);
        t[x] = min(t[x * 2], t[x * 2 + 1]);
    }

    void rangeAdd(int st, int dr, long long v)
    {
        rangeAdd(1, 0, n, st, dr, v);
    }

    long long query(int x, int lx, int rx, int st, int dr)
    {
        if (st <= lx && rx <= dr)
            return t[x];
        push(x);
        int mid = (lx + rx) / 2;
        long long ans = INF;
        if (st <= mid)
            minSelf(ans, query(x * 2, lx, mid, st, dr));
        if (mid < dr)
            minSelf(ans, query(x * 2 + 1, mid + 1, rx, st, dr));
        return ans;
    }

    long long query(int st, int dr)
    {
        return query(1, 0, n, st, dr);
    }
};

long long solve(int n)
{
    SegTree t(n);
    for (int i = 1; i <= n; ++i)
    {
        t.rangeAdd(i, i, t.query(0, i - 1));
        t.rangeAdd(0, i - 1, v[i]);
        for (auto it : rEnd[i])
        {
            int start, cost;
            tie(start, cost) = it;
            t.rangeAdd(start, i, cost);
        }
    }
    return t.t[1];
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    int N = n + m - 1;
    for (int i = 1; i <= N; ++i)
        scanf("%d", &a[i]);
    int cost;
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d", &cost);
        int y = min(i - 1, m - 1);
        int x = i - 1 - y;
        int index = x - y + m;
        int len = min(y + 1, n - x);
        intervals[i] = {index, len, cost};
    }
    long long ans = 0;
    for (int par = 0; par <= 1; ++par)
    {
        int p = get<0>(intervals[2 - par]) % 2;
        int M = (N + p) / 2;
        for (int i = 2 - p; i <= N; i += 2)
            v[(i + p) / 2] = a[i];
        for (int i = 1; i <= M; ++i)

            rEnd[i].clear();

        for (int i = 2 - par; i <= N; i += 2)
        {
            int index, len, cost;
            tie(index, len, cost) = intervals[i];
            index = (index + 1) / 2;
            rEnd[index + len - 1].emplace_back(index, cost);
        }
        ans += solve(M);
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

colouring.cpp: In function 'int main()':
colouring.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
colouring.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
colouring.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         scanf("%d", &cost);
      |         ~~~~~^~~~~~~~~~~~~

• 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