Submission #1186264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186264		KK_1729	Painting Walls (APIO20_paint)	C++20	100 / 100	847 ms	408636 KiB

paint

#include "paint.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
int min(int x, int y){
  if (x < y) return x;
  return y;
}
struct Segtree{
  vector<int> tree;
  int N;
  Segtree(int n){

    while (__builtin_popcount(n) != 1) n++;
    this->N = n;
    tree.resize(2*N+10, 1e9);
  }


  void update(int v, int tl, int tr, int pos, int x){
    // if (pos < tl || pos > tr) return;
    if (tl == tr && tl == pos){
      tree[v] = x;
      return;
    }
    int mid = (tl+tr)/2;
    if (pos <= mid) update(2*v, tl, mid, pos, x);
    else update(2*v+1, mid+1, tr, pos, x);
    tree[v] = min(tree[v*2], tree[v*2+1]);
  }

  int query(int v, int tl, int tr, int l, int r){
    if (l > tr || r < tl) return 1e9;
    if (l <= tl && r >= tr) return tree[v];
    int mid = (tl+tr)/2;
    return min(query(v*2, tl, mid, l, r), query(v*2+1, mid+1, tr, l, r));
  }

  
  void u(int pos, int x){
    update(1, 0, N-1, pos, x);
  }
  int q(int l, int r){
    return query(1, 0, N-1, l, r);
  }
};
void printVector(vector<int> a){
  for (auto x: a) cout << x << " ";
  cout << endl;
}
int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
  


      vector<vector<int>> colour(K+5);
      for (int i = 0; i < N; ++i){
        colour[C[i]].pb(i);
      }
      vector<vector<int>> o(N);
      vector<int> f(K+5);
      for (int i = 0; i < M; i++){
        for (auto x: B[i]){
          f[x]++;
          for (auto item: colour[x]){
            o[item].pb(i);
          }
        }
      }

      vector<int> dp1(M, -1), dp2(M, -1);
      for (auto x: o[N-1]) dp2[x] = N-1;
      vector<int> P(N+5);
      if (M == 1){
        if (f[C[N-1]] > 0) P[N-1] = 1;
      }
      // vector<int> there(M);
      // for (auto x: o[N-1]) there[]
      
      for (int i = N-2; i >= 0; i--){
        for (auto x: o[i]){
          if (dp2[(x+1)%M] >= 0) dp1[x] = dp2[(x+1)%M];
          else dp1[x] = i;
          if (dp1[x] - i >=  M-1) P[i] = 1;
        }

        swap(dp1, dp2);
        for (auto x: o[i+1]) dp1[x] = -1;
      }


      int ans = 0;
      vector<int> dp(N+5, 1e9);
      Segtree seg(N+1);
      seg.u(N, 0);

      for (int i = N-1; i >= 0; i--){
        
        if (N-i >= M){
          // cout << i << endl;
          if (P[i] == 1){
            int o = 1e9;
            dp[i] = 1+seg.q(i+1, i+M);
            seg.u(i, dp[i]);
          }
          
        }
      }
      // printVector(P);
      // printVector(dp);
      if (dp[0] < 1e9) return dp[0];
      
      
      
      return -1;
}

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