Submission #1056136

#TimeUsernameProblemLanguageResultExecution timeMemory
1056136vjudge1Painting Walls (APIO20_paint)C++17
0 / 100
1 ms348 KiB
#include "paint.h" //Dost Seferoğlu #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") using namespace std; //#define int long long #define pii pair<int,int> #define ff first #define ss second #define sp << " " << #define all(cont) cont.begin(),cont.end() #define vi vector<int> const int MOD = 1e9+7,inf = 2e9; const int N = 2e5; struct ST { vi t; ST(int nn) { t.assign(4*nn+1,inf); } void update(int node,int l,int r,int L,int R,int v) { if (l > R || r < L) return; if (l >= L && r <= R) { t[node] = min(t[node],v); return; } int m = (l+r) >> 1; update(2*node,l,m,L,R,v); update(2*node+1,m+1,r,L,R,v); } int query(int node,int l,int r,int p) { if (l == r) return t[node]; int m = (l+r) >>1; if (p<=m) return min(query(2*node,l,m,p),t[node]); else return min(query(2*node+1,m+1,r,p),t[node]); } }; int minimumInstructions( int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) { vector<int> f[K]; for (int i=0;i<M;i++) { for (int j=0;j<A[i];j++) { f[B[i][j]].push_back(i); } } vi go(N,0); go[N-1] = 1; for (int i=N-2;i>=0;i--) { go[i] = 1; for (auto it : f[C[i]]) { auto iter = lower_bound(all(f[C[i+1]]),((it+1)%M)); if (iter != f[C[i+1]].end() && *iter == (it+1)%M) go[i] = max(go[i],min(M,go[i+1]+1)); } } vi dp(N+2,0); ST st(N+1); st.update(1,1,N+1,1,1,0); for (int i=1;i<=N;i++) { dp[i] = st.query(1,1,N+1,i); if (go[i-1] == M) st.update(1,1,N+1,i+1,i+go[i-1],dp[i]+1); } if (st.query(1,1,N+1,N+1) >= inf) return -1; return st.query(1,1,N+1,N+1); }
#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...