제출 #1056250

#제출 시각아이디문제언어결과실행 시간메모리
1056250dosts벽 칠하기 (APIO20_paint)C++17
0 / 100
0 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; vector<bool> cool(N,0); if (M == 1) cool[N-1] = true; vi lst(M,0); for (auto it : f[C[N-1]]) lst[it] = 1; for (int i=N-2;i>=0;i--) { go[i] = 1; vector<pii> ps; 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,lst[*iter]+1)); ps.push_back({it,min(M,lst[*iter]+1)}); } } for (int i=0;i<M;i++) lst[i] = 1; for (auto it : ps) lst[it.ff] = it.ss; if (go[i] == M) cool[i] = true; } 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 (cool[i-1]) st.update(1,1,N+1,i+1,i+M,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...