Submission #1131580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131580		Champ_Naman	벽 칠하기 (APIO20_paint)	C++20	63 / 100	594 ms	589824 KiB

paint

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

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

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 : st[c[n-1]]){
      pre[j] = n-1;
      rt[n-1].push_back(n-1);
   }
   for(int i=n-2; i>=0; i--){
      for(int j : st[c[i]]){
         rt[i].push_back(pre[(j+1) % m] == -1 ? i : pre[(j+1) % 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]] = rt[i][j]; 
   }

   int ans = 0;
   for(int i=0; i<n;){
      int mx = -1e9;
      for(int j=0; j<st[c[i]].size(); j++){
         if(rt[i][j] - lt[i][j] + 1 >= m){
            mx = max(mx, min(i+m-1, rt[i][j]));
         }
      }

      if(mx == -1e9) return -1;
      i = mx+1;
      ans++;
   }

   return ans;
}

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