제출 #292515

#제출 시각아이디문제언어결과실행 시간메모리
292515amoo_safarPainting Walls (APIO20_paint)C++17
100 / 100
507 ms13688 KiB
#include "paint.h" #include <bits/stdc++.h> #define F first #define S second #define pb push_back #define all(x) x.begin(), x.end() using namespace std; typedef pair<int, int> pii; const int N = 1e5 + 10; const int Log = 20; vector<int> Lov[N]; int R[N], L[N], ps[N]; int minimumInstructions(int n, int m, int k, vector<int> C, vector<int> A, vector<vector<int>> B){ memset(R, 0, sizeof R); memset(L, 0, sizeof L); memset(ps, 0, sizeof ps); for(int i = 0; i < m; i++){ assert(A[i] == (int) B[i].size()); for(auto x : B[i]){ Lov[x].pb(i); } } int col; for(int i = 0; i < n; i++){ col = C[i]; assert(col < k); for(auto &x : Lov[col]){ if(x <= i && R[i - x] == x) R[i - x] ++; } } for(int i = n - 1; i >= 0; i--){ col = C[i]; for(auto &x : Lov[col]){ if((m - 1 - x) <= n - 1 - i && L[i + (m - 1 - x) + 1] == (m - 1 - x)) L[i + (m - 1 - x) + 1] ++; } } /* map<pii, int> mp; for(int i = 0; i < m; i++){ assert(A[i] == (int) B[i].size()); for(auto x : B[i]){ Lov[x].pb(i); } } */ int ls, rs; for(int i = 0; i <= n; i++){ if(L[i] + R[i] < m) continue; ls = i - L[i]; rs = ls + ((R[i] + L[i]) - m); rs = min(rs, n); ls = max(ls, 0); ps[ls] ++; ps[rs + 1] --; } for(int i = 1; i <= n; i++) ps[i] += ps[i - 1]; /* vector<int> pos; for(int i = 0; i < n; i++){ if(i + m <= n && ps[i] > 0) pos.pb(i); } */ int laa = -1, la = 0, ans = 0; while(la < n){ bool flg = false; for(int i = la; i > laa; i--){ if(i + m <= n && ps[i] > 0){ laa = la; la = i + m; flg = true; break; } } if(flg) ans ++; else return -1; } return ans; } /* 8 3 5 3 3 1 3 4 4 2 2 3 0 1 2 2 2 3 2 3 4 5 4 4 1 0 1 2 2 2 0 1 1 1 1 2 1 3 */
#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...