Submission #697149

#	Time	Username	Problem	Language	Result	Execution time	Memory
697149		whqkrtk04	Painting Walls (APIO20_paint)	C++17	28 / 100	1249 ms	524288 KiB

paint

#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;
    if(chk.empty()) {
        for(int i = 0; i < M; i++) ret.push_back(i);
        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); }
};

int minimumInstructions(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;
    for(int i = 0; i < M; i++) {
        chk[C[i]].push_back(i);
        for(auto j : B[i]) can[j].push_back(i);
    }
    //cout << " " << chk;
    //cout << " " << can;
    for(int i = 0; i < K; i++) {
        verdict[i] = evaluate(M, chk[i], can[i]);
        for(auto j : verdict[i]) if(++cnt[j] == K) macnt++;
    }
    //cout << M-1 << "\n" << " " << verdict;
    can_paint[M-1] = macnt > 0;
    for(int i = M; i < N; i++) {
        for(auto j : verdict[C[i-M]]) if(cnt[j]-- == K) macnt--;
        for(auto j : verdict[C[i]]) if(cnt[j]-- == K) macnt--;
        chk[C[i-M]].pop_front();
        chk[C[i]].push_back(i);
        verdict[C[i-M]] = evaluate(M, chk[C[i-M]], can[C[i-M]]);
        verdict[C[i]] = evaluate(M, chk[C[i]], can[C[i]]);
        for(auto j : verdict[C[i-M]]) if(++cnt[j] == K) macnt++;
        for(auto j : verdict[C[i]]) if(++cnt[j] == K) macnt++;
        //cout << i << "\n" << " " << verdict;
        can_paint[i] = macnt > 0;
    }
    //cout << can_paint << "\n";
    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 (stderr)

paint.cpp: In function 'std::vector<int> evaluate(int, std::deque<int>&, std::vector<int>&)':
paint.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i = 0; i < can.size(); i++) {
      |                    ~~^~~~~~~~~~~~
paint.cpp:31:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         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:78: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:122:62:   required from here
paint.cpp:50:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |    init(i<<1, s, s+e>>1, A);
      |                  ~^~
paint.cpp:51:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |    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:80: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:123:42:   required from here
paint.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |    update(i<<1, s, s+e>>1, j, x);
      |                    ~^~
paint.cpp:61:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |    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:81: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:126:38:   required from here
paint.cpp:69:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
      |                         ~^~
paint.cpp:69:54: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
      |                                                     ~^~

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