Submission #1173615

#TimeUsernameProblemLanguageResultExecution timeMemory
1173615PlayVoltzPainting Walls (APIO20_paint)C++20
100 / 100
446 ms13148 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; #define pb push_back bool can[100005]; int m, cc[50005], freq[50005]; vector<int> c, in[100005]; void add(int i){ for (auto a:in[c[i]])--freq[cc[(i-a%m+m)%m]], ++cc[(i-a%m+m)%m], ++freq[cc[(i-a%m+m)%m]]; } void del(int i){ for (auto a:in[c[i]])--freq[cc[(i-a%m+m)%m]], --cc[(i-a%m+m)%m], ++freq[cc[(i-a%m+m)%m]]; } int minimumInstructions(int n, int M, int k, vector<int> C, vector<int> a, vector<vector<int> > b){ m=M; c=C; for (int i=0; i<m; ++i)for (auto num:b[i])in[num].pb(i); freq[0]=m; for (int i=0; i<m; ++i)add(i); can[0]=!!freq[m]; for (int i=m; i<n; ++i)del(i-m), add(i), can[i-m+1]=!!freq[m]; int ans=0, p=-1, i=0; while (1){ int mx=-1; while (p<i)if (can[++p])mx=p+m; ++ans; if (mx>=n)return ans; if (mx==-1)return -1; i=mx; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...