제출 #999782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999782		underwaterkillerwhale	벽 칠하기 (APIO20_paint)	C++17	63 / 100	1571 ms	30036 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N  = 2e5 + 7;
const int Mod = 998244353;
const int szBL = 916;
const int INF = 1e9;
const int BASE = 137;
int n, m, K;

vector<int> A, C;
vector<vector<int>> B;

namespace sub1  {
    int idxA[N], f[N];

    bool check () {
        rep (i, 0, m - 1) iter (&col, B[i]) f[col]++;
        return *max_element (f, f + K) <= 1;
    }

    int solution() {
        rep (i, 0, K - 1) idxA[i] = -1;
        rep (i, 0, m - 1) {
            iter (&col, B[i]) idxA[col] = i;
        }
        int st = idxA[C[0]];
        if (st == -1) return -1;
        int res = 1;
        rep (i, 1, n - 1) {
            if (i % m == 0) ++res;
            (st += 1) %= m;
            int pos = lower_bound (ALL(B[st]), C[i]) - B[st].begin();
            if (pos == SZ(B[st]) || B[st][pos] != C[i]) return -1;
        }
        return res;
    }
}

namespace sub4 {
    const int N2 = 20000 + 2;
    const int M2 = 2000 + 2;
    int dp[N2][M2 * 2], f[N];
    bool ok[N2];

    vector<int> posC[N];

    struct Segment_Tree {
        int Range;
        int st[N << 2];

        void init (int n) {
            Range = n;
            rep (i, 1, n << 2) {
                st[i] = INF;
            }
        }

        void update (int id, int l, int r, int pos, int val) {
            if (l > pos || r < pos) return;
            if (l == r) {
                st[id] = val;
                return;
            }
            int mid = l + r >> 1;
            update (id << 1, l, mid, pos, val);
            update (id << 1 | 1, mid + 1, r, pos, val);
            st[id] = min(st[id << 1], st[id << 1 | 1]);
        }
        int get (int id, int l, int r, int u, int v) {
            if (l > v || r < u) return INF;
            if (l >= u && r <= v) return st[id];
            int mid = l + r >> 1;
            return min (get (id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v));
        }

        void update (int pos, int val ) {
            update (1, 1, Range, pos, val);
        }
        int get (int u, int v) {
            return get (1, 1, Range, u, v);
        }
    }ST;

    int solution() {
        A.resize (2 * m);
        B.resize (2 * m);
        rep (i, m, 2 * m - 1) {
            A[i] = A[i - m];
            B[i] = B[i - m];
        }
        rep (i, 0, n - 1) posC[C[i]].push_back(i);
        rep (j, 0, 2 * m - 1) {
            iter (&col, B[j])
                iter (&pos, posC[col]) {
                dp[pos][j] = 1;
            }
        }
        reb (i, n - 1, 0) {
            reb (j, 2 * m - 1, 0) {
                if (dp[i][j] != 0) dp[i][j] = dp[i + 1][j + 1] + 1;
                if (dp[i][j] >= m) ok[i + 1] = 1;
            }
        }
        rep (i, 1, n) f[i] = INF;
        ST.init(n);
        f[m] = ok[1] ? 1 : INF;
        ST.update (m, f[m]);
        rep (i, 2, n - m + 1) {
            if (ok[i]) {
                f[i + m - 1] = ST.get (i - 1, i + m - 1) + 1;
                ST.update (i + m - 1, f[i + m - 1]);
            }
        }
        if (f[n] < INF) return f[n];
        else return -1;
    }
}

namespace sub5 {
    struct Segment_Tree {
        int Range;
        int st[N << 2];

        void init (int n) {
            Range = n;
            rep (i, 1, n << 2) {
                st[i] = 0;
            }
        }

        void update (int id, int l, int r, int pos, int val) {
            if (l > pos || r < pos) return;
            if (l == r) {
                st[id] += val;
                return;
            }
            int mid = l + r >> 1;
            update (id << 1, l, mid, pos, val);
            update (id << 1 | 1, mid + 1, r, pos, val);
            st[id] = max(st[id << 1], st[id << 1 | 1]);
        }
        void update (int pos, int val ) {
            update (1, 1, Range, pos + 1, val);
        }
    }tot; ///rotation
    struct Segment_Tree2 {
        int Range;
        int st[N << 2];

        void init (int n) {
            Range = n;
            rep (i, 1, n << 2) {
                st[i] = INF;
            }
        }

        void update (int id, int l, int r, int pos, int val) {
            if (l > pos || r < pos) return;
            if (l == r) {
                st[id] = val;
                return;
            }
            int mid = l + r >> 1;
            update (id << 1, l, mid, pos, val);
            update (id << 1 | 1, mid + 1, r, pos, val);
            st[id] = min(st[id << 1], st[id << 1 | 1]);
        }
        int get (int id, int l, int r, int u, int v) {
            if (l > v || r < u) return INF;
            if (l >= u && r <= v) return st[id];
            int mid = l + r >> 1;
            return min (get (id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v));
        }

        void update (int pos, int val ) {
            update (1, 1, Range, pos, val);
        }
        int get (int u, int v) {
            return get (1, 1, Range, u, v);
        }
    }ST;

    vector<int> F[N];
    bool ok[N];
    int f[N];

    int solution() {
        rep (i, 0, m - 1) {
            iter (&col, B[i]) F[col].push_back(i);
        }
        tot.init (m);
        rep (i, 0, m - 1) {
            iter (&pos, F[C[i]]) {
                tot.update((pos - i % m + m) % m, 1);
            }
        }
        if (tot.st[1] == m) ok[1] = 1;
        rep (i, 1, n - m) {
            iter (&pos, F[C[i - 1]]) {
                tot.update((pos - (i - 1) % m + m) % m, -1);
            }
            iter (&pos, F[C[i + m - 1]]) {
                tot.update ((pos - (i - 1) % m + m) % m, 1);
            }
            if (tot.st[1] == m) ok[i + 1] = 1;
        }
        rep (i, 1, n) f[i] = INF;
        ST.init(n);
        f[m] = ok[1] ? 1 : INF;
        ST.update (m, f[m]);
        rep (i, 2, n - m + 1) {
            if (ok[i]) {
                f[i + m - 1] = ST.get (i - 1, i + m - 1) + 1;
                ST.update (i + m - 1, f[i + m - 1]);
            }
        }
        if (f[n] < INF) return f[n];
        else return -1;
    }
}

int minimumInstructions (int _n, int _m, int _K, vector<int> _C, vector<int> _A, vector<vector<int>> _B) {
//void solution() {
    n = _n;
    m = _m;
    K = _K;
    C = _C;
    A = _A;
    B = _B;
//    cin >> n >> m >> K;
//    C.resize(n);
//    rep (i, 0, n - 1) {
//        cin >> C[i];
//
//    }
//    A.resize (m);
//    B.resize (m);
//    rep (i, 0, m - 1) {
//        cin >> A[i];
//        B[i].resize (A[i]);
//        rep (j, 0, A[i] - 1) {
//            cin >> B[i][j];
//        }
//    }
//    if (sub1 :: check())
//        return sub1 :: solution();
////        cout << sub1 :: solution() <<"\n";
//    else if (n <= 20000 && m <= 2000)
//        return sub4 :: solution();
////        cout << sub4 :: solution() <<"\n";
//    else
        return sub5 :: solution();
//        cout << sub5 :: solution() <<"\n";
}

//#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
//int main () {
//    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
////    file ("c");
//    int num_Test = 1;
////    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}
/*
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4



5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3

*/

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In member function 'void sub4::Segment_Tree::update(int, int, int, int, int)':
paint.cpp:84:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |             int mid = l + r >> 1;
      |                       ~~^~~
paint.cpp: In member function 'int sub4::Segment_Tree::get(int, int, int, int, int)':
paint.cpp:92:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |             int mid = l + r >> 1;
      |                       ~~^~~
paint.cpp: In member function 'void sub5::Segment_Tree::update(int, int, int, int, int)':
paint.cpp:157:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  157 |             int mid = l + r >> 1;
      |                       ~~^~~
paint.cpp: In member function 'void sub5::Segment_Tree2::update(int, int, int, int, int)':
paint.cpp:183:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  183 |             int mid = l + r >> 1;
      |                       ~~^~~
paint.cpp: In member function 'int sub5::Segment_Tree2::get(int, int, int, int, int)':
paint.cpp:191:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  191 |             int mid = l + r >> 1;
      |                       ~~^~~

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