Submission #571202

#	Time	Username	Problem	Language	Result	Execution time	Memory
571202		MadokaMagicaFan	Painting Walls (APIO20_paint)	C++17	0 / 100	1 ms	212 KiB

paint

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define all(v)                      v.begin(), v.end()
#define rall(v)                     v.rbegin(), v.rend()
#define sz(v)                       ((int)v.size())

#define forn(i,n)                   for(int i = 0; i < n; ++i)
#define forbe(i,b,e)                for(int i = b; i < e; ++i)

#define pb                          push_back

#define pry                         puts("YES")
#define prn                         puts("NO")
#define endl                        '\n'

#define fst                         first
#define scn                         second

struct node{
    int sb, se;
    int fb;
};

vector<node> ns;

struct SGT {
    int n;
    vector<int> t;

    void
    init(int _n)
    {
        n = _n;
        t.resize(4*n, 0);
    }

    void
    update(int i, int l, int r, int tl, int tr)
    {
        if (tr < l || r < tl)
            return;

        if (tl <= l && r <= tr) {
            t[i] = 1;
            return;
        }

        if (l == r)
            return;
        int mid = (l + r) >> 1;
        update(i>>1, l, mid, tl, tr);
        update(i>>1|1, mid+1, r, tl, tr);
        return;
    }

    void
    update(int l, int r)
    {
        update(0, 0, n-1, max(l,0), min(r,n-1));
        return;
    }

    int
    query(int i, int l, int r, int x)
    {
        int ans = 0;
        if (l > x || r < x)
            return 0;

        if (l <= x && r >= x) {
            ans = t[i];
        }

        if (l == r)
            return ans;

        int mid = (l + r) >> 1;
        ans += query(i>>1, l, mid, x);
        ans += query(i>>1|1, mid+1, r, x);

        return ans;
    }

    int
    query(int x)
    {
        return query(0, 0,n-1,x);
    }
};

int
minimumInstructions(int n, int m, int k, vector<int> c,
        vector<int> a, vector<vector<int>> b)
{
    vector<int> has[k];
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < a[i]; ++j) {
            has[b[i][j]].pb(i);
        }
    }

    ns.resize(m+n);
    for (int i = 0; i < n+m; ++i) {
        ns[i].sb = -2;
        ns[i].se = -2;
        ns[i].fb = -1;
    }

    SGT tr;
    tr.init(n);

    for (int i = m; i < n+m; ++i) {
        for (int u : has[c[i-m]]) {
            if (i - u > -1) {
                if (ns[i-u].se + 1 == u) {
                    ++ns[i-u].se;
                } else {
                    ns[i-u].se = u;
                    ns[i-u].sb = u;
                }
            }
            if (i - u - m > -1) {
                if (ns[i-u-m].fb == u - 1)
                    ns[i-u-m].fb = u;
            }
        }
    }

    for (int i = 0; i < n+m; ++i) {
        if (ns[i].sb == 0 && ns[i].se == n-1) {
            tr.update(i-m,i-m);
        }

        if (ns[i].se != m-1 || ns[i].fb < 0)
            continue;

        if (ns[i].sb > ns[i].fb + 1)
            continue;
        /* cout << i-m << ' ' << ns[i].sb << ' ' << ns[i].se  << ' ' << ns[i].fb << endl; */

        tr.update(i - m + ns[i].sb, i + ns[i].fb +1 - m);
    }

    /* for (int i = 0; i < n; ++i) { */
    /*     cout << tr.query(i) << ' '; */
    /* } */
    /* cout <<endl; */

    if (!tr.query(0))
        return -1;

    int r = m-1;
    int l = 0;

    int ans = 1;
    bool t = 1;

    while (t) {
        t = 0;
        /* cout << l << ' ' << r << endl; */
        for (int i = min(r,n-m); i > l; --i) {
            if (tr.query(i)) {
                t = 1;
                l = i;
                r = i + m;
                ++ans;
                if (i + m - 1 >= n-1)
                    return ans;
            }
        }
    }


    return -1;
}

#ifdef ONPC
void
solve()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> c(n);
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }

    vector<int> a(m);
    for (int i = 0; i < m; ++i) {
        cin >> a[i];
    }

    vector<vector<int>> b(m);

    for (int i = 0; i < m; ++i) {
        b[i].resize(a[i]);
        for (int j = 0; j < a[i]; ++j) {
            cin >> b[i][j];
        }
    }


    cout << minimumInstructions(n, m, k, c, a, b) << endl;
}

int32_t
main()
{
    freopen("in", "r", stdin);
    int t = 1;
    cin >> t;
    while(t--)
        solve();
}
#endif

• Subtask 1: 0 / 12
• Subtask 2: 0 / 15
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 37