#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const deque<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
vector<int> evaluate(int M, deque<int> &chk, vector<int> &can) {
vector<int> ret;
if(chk.size() > can.size()) return ret;
for(int i = 0; i < can.size(); i++) {
int diff = ((can[i]-chk[0])%M+M)%M;
bool valid = true;
for(int j = 0; j < chk.size(); j++) {
int tmp = ((chk[j]+diff)%M+M)%M;
auto iter = lower_bound(can.begin(), can.end(), tmp);
if(iter == can.end() || *iter != tmp) valid = false;
}
if(valid) ret.push_back(diff);
}
return ret;
}
template <typename node_seg, typename node_query = node_seg, typename index_t = int>
class Segtree {
private:
const size_t n;
std::vector<node_seg> seg;
void init(const size_t i, const index_t s, const index_t e, const std::vector<node_seg> &A) {
if(s+1 == e) seg[i] = A[s];
else {
init(i<<1, s, s+e>>1, A);
init(i<<1|1, s+e>>1, e, A);
seg[i] = seg[i<<1]+seg[i<<1|1];
}
}
void update(const size_t i, const index_t s, const index_t e, const index_t j, const node_query &x) {
if(j >= e || s > j) return;
if(s+1 == e) seg[i] += x;
else {
update(i<<1, s, s+e>>1, j, x);
update(i<<1|1, s+e>>1, e, j, x);
seg[i] = seg[i<<1]+seg[i<<1|1];
}
}
node_seg query(const size_t i, const index_t s, const index_t e, const index_t l, const index_t r) const {
if(e <= l || r <= s) return node_seg::inf();
if(l <= s && e <= r) return seg[i];
return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
}
public:
Segtree(const int n) : n(n) {
seg.resize(4*n, node_seg::inf());
}
Segtree(const std::vector<node_seg> &A) : n(A.size()) {
seg.resize(4*n, node_seg::inf());
init(1, 0, n, A);
}
void update(const index_t j, const node_query &x) { update(1, 0, n, j, x); }
node_seg query(const index_t l, const index_t r) const { return query(1, 0, n, l, r); }
};
struct min_node {
int x;
static min_node inf() { return {INF}; }
min_node operator+(const min_node &y) { return {min(x, y.x)}; }
void operator+=(const min_node &y) { x = min(x, y.x); }
};
void add(int M, int idx, int &uniqcnt, int &macnt,
vector<int> &verdict, vector<int> &cnt, deque<int> &chk, vector<int> &can) {
if(chk.empty()) uniqcnt++, macnt = 0;
else for(auto j : verdict) if(cnt[j]-- == uniqcnt) macnt--;
chk.push_back(idx);
verdict = evaluate(M, chk, can);
for(auto j : verdict) if(++cnt[j] == uniqcnt) macnt++;
}
void sub(int M, int &uniqcnt, int &macnt,
vector<int> &verdict, vector<int> &cnt, deque<int> &chk, vector<int> &can) {
for(auto j : verdict) if(cnt[j]-- == uniqcnt) macnt--;
chk.pop_front();
if(chk.empty()) uniqcnt--, verdict.clear();
else verdict = evaluate(M, chk, can);
for(auto j : verdict) if(++cnt[j] == uniqcnt) macnt++;
}
vector<bool> solve(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
vector<deque<int>> chk(K);
vector<vector<int>> verdict(K), can(K);
vector<int> cnt(M, 0);
vector<bool> can_paint(N, false);
int macnt = 0, uniqcnt = 0;
for(int i = 0; i < M; i++) for(auto j : B[i]) can[j].push_back(i);
for(int i = 0; i < K; i++) {
if(chk[i].empty()) continue;
verdict[i] = evaluate(M, chk[i], can[i]);
for(auto j : verdict[i]) if(++cnt[j] == uniqcnt) macnt++;
//cout << i << "\n " << verdict;
}
for(int i = 0; i < M; i++) add(M, i, uniqcnt, macnt, verdict[C[i]], cnt, chk[C[i]], can[C[i]]);
can_paint[M-1] = macnt > 0;
for(int i = M; i < N; i++) {
add(M, i, uniqcnt, macnt, verdict[C[i]], cnt, chk[C[i]], can[C[i]]);
sub(M, uniqcnt, macnt, verdict[C[i-M]], cnt, chk[C[i-M]], can[C[i-M]]);
can_paint[i] = macnt > 0;
//cout << i << "\n " << verdict;
}
return can_paint;
}
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
vector<bool> can_paint = solve(N, M, K, C, A, B);
//cout << can_paint;
Segtree<min_node> dp(vector<min_node>(N, min_node::inf()));
if(can_paint[M-1]) dp.update(M-1, {1});
for(int i = M; i < N; i++) {
if(can_paint[i]) {
int tmp = dp.query(i-M, i).x;
dp.update(i, {++tmp});
}
}
int ans = dp.query(N-1, N).x;
if(ans == INF) return -1;
else return ans;
}
Compilation message
paint.cpp: In function 'std::vector<int> evaluate(int, std::deque<int>&, std::vector<int>&)':
paint.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int i = 0; i < can.size(); i++) {
| ~~^~~~~~~~~~~~
paint.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int j = 0; j < chk.size(); j++) {
| ~~^~~~~~~~~~~~
paint.cpp: In instantiation of 'void Segtree<node_seg, node_query, index_t>::init(size_t, index_t, index_t, const std::vector<_Tp>&) [with node_seg = min_node; node_query = min_node; index_t = int; size_t = long unsigned int]':
paint.cpp:74:3: required from 'Segtree<node_seg, node_query, index_t>::Segtree(const std::vector<_Tp>&) [with node_seg = min_node; node_query = min_node; index_t = int]'
paint.cpp:132:62: required from here
paint.cpp:46:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | init(i<<1, s, s+e>>1, A);
| ~^~
paint.cpp:47:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | init(i<<1|1, s+e>>1, e, A);
| ~^~
paint.cpp: In instantiation of 'void Segtree<node_seg, node_query, index_t>::update(size_t, index_t, index_t, index_t, const node_query&) [with node_seg = min_node; node_query = min_node; index_t = int; size_t = long unsigned int]':
paint.cpp:76:60: required from 'void Segtree<node_seg, node_query, index_t>::update(index_t, const node_query&) [with node_seg = min_node; node_query = min_node; index_t = int]'
paint.cpp:133:42: required from here
paint.cpp:56:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | update(i<<1, s, s+e>>1, j, x);
| ~^~
paint.cpp:57:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | update(i<<1|1, s+e>>1, e, j, x);
| ~^~
paint.cpp: In instantiation of 'node_seg Segtree<node_seg, node_query, index_t>::query(size_t, index_t, index_t, index_t, index_t) const [with node_seg = min_node; node_query = min_node; index_t = int; size_t = long unsigned int]':
paint.cpp:77:71: required from 'node_seg Segtree<node_seg, node_query, index_t>::query(index_t, index_t) const [with node_seg = min_node; node_query = min_node; index_t = int]'
paint.cpp:136:38: required from here
paint.cpp:65:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
| ~^~
paint.cpp:65:54: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
