Submission #1203218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203218		O_Elmasry	Painting Walls (APIO20_paint)	C++20	28 / 100	1600 ms	160580 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#include <vector>
using ll = int;
const ll INF = 1e9;
struct Segment_Tree{
  int sz = 1;
  vector<int>tree;
  Segment_Tree(int N){
    while(sz < N)sz <<= 1;
    tree.resize(sz * 2, INF);
  }
  #define left node * 2 + 1
  #define right node * 2 + 2
  void update(int idx, int val, int node, int l, int r){
    if(l == r)return void(tree[node] = val);
    int mid = l + r >> 1;
    if(idx <= mid)update(idx, val, left, l, mid);
    else update(idx, val, right, mid + 1, r);
    tree[node] = min(tree[left], tree[right]);
  }
  void update(int idx, int val){
    update(idx, val, 0, 0, sz - 1);
  }

  int query(int lq, int rq, int node, int l, int r){
    if(l > rq || r < lq)return INF;
    if(l >= lq && r <= rq)return tree[node];
    int mid = l + r >> 1;
    return min(query(lq, rq, left, l, mid), query(lq, rq, right, mid + 1, r));
  }
  int query(int lq, int rq){
    return query(lq, rq, 0, 0, sz - 1);
  }
  #undef left
  #undef right
};
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
  vector<ll>dp(N, INF);
  vector<vector<int>>comp(M, vector<int>(N));
  vector<vector<int>>color(K);
  for(int j = 0;j < M;j++){
    for(auto x : B[j]){
      color[x].push_back(j);
    }
  }
  for(int i = 0;i < N;i++){
    for(auto j : color[C[i]]){
      comp[j][i] = 1;
    }
  }
  auto check = [&](int x, int y){
    bool ok = 1;
    for(int i = 0;i < M;i++){
      int xx = (x + i) % M;
      int yy = y + i;
      ok &= comp[xx][yy];
    }
    return ok;
  };
  Segment_Tree seg(N);
  for(int i = M - 1;i < N;i++){
    bool ok = 0;
    for(int j = 0;j < M;j++){
      ok |= check(j, i - M + 1);
      if(ok)break;
    }
    if(!ok)continue;
    if(i == M - 1){
      dp[i] = 1;
    }
    int L = max(0, i - M);
    ll Min = seg.query(L, i - 1);
    dp[i] = min(dp[i] , Min + 1);
    seg.update(i, dp[i]);
  }
  return (dp[N - 1] >= INF ? -1 : dp[N - 1]);
}

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