oj.uz

Submission #741434

# Submission time Handle Problem Language Result Execution time Memory
741434 2023-05-14T05:15:40 Z penguin133 Painting Walls (APIO20_paint) C++17
0 / 100
 6 ms 9684 KB 
#include <bits/stdc++.h>
using namespace std;

#include "paint.h"
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

bool ok[200005];
vector <int> brr[200005], grr[200005];
int dp[200005];
int stuf[200005];

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
  for(int i=0;i<M;i++){
	  for(auto j : B[i])brr[j].push_back(i);
  }
  set <int> ms;
  for(int i=0;i<M;i++)stuf[i] = M;
  for(int i=0;i<M-1;i++){
	for(auto j : brr[C[i]])stuf[(j - i + 1000 * M) % M]--;  
  }
  for(int i=M-1;i<N;i++){
	  for(auto j : brr[C[i]]){
		  stuf[(j - i + 1000 * M) % M]--;
		  int tmp = (j - i + 1000 * M)%M;
		  if(stuf[tmp] == 0)ms.insert(tmp);
	  }
	  int rv = i - (M - 1) - 1;
	  if(rv >= 0){
		  for(auto j : brr[C[rv]]){
			  stuf[(j - rv + 1000 * M) % M]++;
			  int tmp = (j - rv + 1000 * M) % M;
			  if(stuf[tmp] == 1)ms.erase(tmp);
		  }
	  }
	  if(!ms.empty())ok[i] = 1;
  }
  for(int i = 0; i < M - 1; i++)dp[i] = 2e9;
  deque <pi> dq;
  dq.push_back({0, -1});
  for(int i=M - 1;i<N;i++){
	  dp[i] = 2e9;
	  //cout << ok[i] << ' ';
	  if(!dq.empty() && dq.front().se < i - M)dq.pop_front();
	  if(ok[i]){
		  int tmp= 2e9;
		  if(i == M - 1)tmp = 0;
		  for(int j = i - 1; j >= max(0, i - M); j--)tmp = min(tmp, dp[j]);
		  dp[i] = tmp + 1;
	  }
	  while(!dq.empty() && dq.back().fi > dp[i])dq.pop_back();
	  dq.push_back({dp[i], i});
  }
  return (dp[N - 1] == 2e9 ? -1 : dp[N - 1]);
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9604 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Incorrect 5 ms 9684 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9604 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Incorrect 5 ms 9684 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9604 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Incorrect 5 ms 9684 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9604 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Incorrect 5 ms 9684 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9604 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Incorrect 5 ms 9684 KB Output isn't correct
10 Halted 0 ms 0 KB -