Submission #1219230

#TimeUsernameProblemLanguageResultExecution timeMemory
1219230Mans21Painting Walls (APIO20_paint)C++20
63 / 100
375 ms589824 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; const int maxn = 100'000 + 12; vector<int> g[maxn]; vector<int> upd[maxn]; int Cur[maxn], cnt[maxn]; bool is[maxn]; 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++) { sort(B[i].begin(), B[i].end()); for(int x : B[i]) { g[x].push_back(i); } } for(int j = 0; j < n; j++) { for(int i : g[c[j]]) { int val = (i - j) % m; if(val < 0) val += m; val++; upd[max(0, j - m + 1)].push_back(val); upd[j + 1].push_back(-val); } } for(int i = 0; i < n; i++) { for(auto val : upd[i]) { int x = abs(val), y = x / val; cnt[Cur[x]]--; Cur[x] += y; cnt[Cur[x]]++; } is[i] = (cnt[m] > 0); } int ans = 0, last = -1e9, cur = -1e9; for(int i = 0; i < n; i++) { if(is[i]) last = i; if(i - cur >= m) { if(i - last >= m) { return -1; } cur = last; ans++; } } return ans; }
#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...