Submission #1216207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216207		mychecksedad	Painting Walls (APIO20_paint)	C++20	63 / 100	1596 ms	13556 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


int sz, T[N];
void build(int n){
  sz=n;
  for(int i = 0; i <= 2*sz+2; ++i) T[i] = 0;
}
void add(int v, int x){
  ++v;
  v += sz;
  T[v] += x;
  for(v >>= 1; v; v >>= 1) T[v] = max(T[v<<1], T[v<<1|1]);
}

int minimumInstructions(int n, int m, int k, std::vector<int> CC, std::vector<int> A, std::vector<std::vector<int>> B) {
  vector<vi> COL(k);
  for(int i = 0; i < m; ++i){
    for(int j = 0; j < A[i]; ++j) COL[B[i][j]].pb(i);
  }
      
  int C = m;
  // int D = m;
  build(C);
  for(int j = 0; j + 1 < m; ++j){
    for(int pos: COL[CC[j]]) add((j-pos+C)%C, 1);
  }
  vector<bool> ok(n);
  for(int i = 0; i <= n - m; ++i){
    for(int pos: COL[CC[i + m - 1]]) add((i+m-1-pos+C)%C, 1);
    
    // cerr << T[1] << ' ';
    if(T[1] == m){
      ok[i] = 1;
    }

    for(int pos: COL[CC[i]]) add((i-pos+C)%C, -1);
  }

  if(ok[0] == 0 || ok[n-m] == 0) return -1;
  vector<pii> P;
  P.pb({0, 1});
  int last = 0;
  for(int i = 1; i <= n-m; ++i){
    if(ok[i]) last = i;
    if(last <= i - m) return -1;
    if(ok[i]){
      int pos = lower_bound(all(P), pii{i - m, -1}) - P.begin();
      P.pb({i, P[pos].ss + 1});
    }
    // cerr << dp[i] << ' ';
  }

  return P.back().ss;
}

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