Submission #1183139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183139		loom	Painting Walls (APIO20_paint)	C++20	100 / 100	820 ms	408920 KiB

paint

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

const int N = 1e5;
vector<int> st[N], lt[N];
vector<int> pre(N/2, -1);
vector<int> mx(N, -1e9);

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b){
   for(int i=0; i<m; i++){
      for(int j=0; j<a[i]; j++){
         st[b[i][j]].push_back(i);
      }
   }

   for(int j : st[c[0]]){
      pre[j] = 0;
      lt[0].push_back(0);
   }
   for(int i=1; i<n; i++){
      for(int j : st[c[i]]){
         lt[i].push_back(pre[(j-1+m) % m] == -1 ? i : pre[(j-1+m) % m]);
      }

      for(int j : st[c[i-1]]) pre[j] = -1;
      for(int j=0; j<st[c[i]].size(); j++) pre[st[c[i]][j]] = lt[i][j]; 
   }

   fill(pre.begin(), pre.end(), -1);
   for(int j=0; j<st[c[n-1]].size(); j++){
      pre[st[c[n-1]][j]] = n-1;
      if(n-1 - lt[n-1][j] + 1 >= m) mx[n-1] = max(mx[n-1], n-1);
   }
   for(int i=n-2; i>=0; i--){
      vector<int> rt;
      for(int j=0; j<st[c[i]].size(); j++){
         int val = pre[(st[c[i]][j]+1) % m] == -1 ? i : pre[(st[c[i]][j]+1) % m];
         if(val - lt[i][j] + 1 >= m) mx[i] = max(mx[i], val);
         rt.push_back(val);
      }

      for(int j : st[c[i+1]]) pre[j] = -1;
      for(int j=0; j<st[c[i]].size(); j++) pre[st[c[i]][j]] = rt[j]; 
   }

   int ans = 0;
   for(int i=0; i<n;){
      if(mx[i] == -1e9) return -1;
      i = min(i+m, mx[i]+1);
      ans++;
   }

   return ans;
}

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