제출 #571578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
571578		MadokaMagicaFan	벽 칠하기 (APIO20_paint)	C++14	0 / 100	1 ms	292 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;

template<typename T>
struct BIT{
    int n;
    vector<T> fen;
    BIT(int n){
        this->n = n;
        fen.assign(n,0);
    }
    BIT(vector<T> a) : BIT(a.size()){
        for(int i = 0; i < n; ++i) add(i,a[i]);
    }
    void add(int x, T v){
        for(; x < n; x |= x+1) fen[x] += v;
    }
    T query(int x){
        T res = 0;
        for(; x >= 0; x = (x&(x+1))-1)
            res += fen[x];
        return res;
    }
    T query(int l, int r){
        return query(r) - query(l-1);
    }
};

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;
    }

    BIT<int> tr(n+1);

    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 == m-1 && i >= m) {
            tr.add(i-m,1);
            tr.add(i-m+1,-1);
        }

        /* cout << i-m << ' ' << ns[i].sb << ' ' << ns[i].se  << ' ' << ns[i].fb << endl; */
        if (ns[i].se != m-1 || ns[i].fb < 0)
            continue;

        if (ns[i].sb > ns[i].fb + 1)
            continue;

        if (i -m + ns[i].fb + 1 >= 0) {
            tr.add(i-m+ns[i].sb,1);
            tr.add(i-m+1+ns[i].fb,1);
        }
    }


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

    int r = m;
    int l = 0;

    if (m == n)
        return 1;

    int ans = 1;
    bool t = 1;

    while (t) {
        t = 0;
        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