Submission #1226091

#TimeUsernameProblemLanguageResultExecution timeMemory
1226091midiPainting Walls (APIO20_paint)C++20
63 / 100
652 ms589824 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define vc vector typedef vc<ll> vcll; typedef vc<bool> vcb; #define pr pair typedef pr<ll,ll> prll; #define fi first #define se second #define sz size #define mp make_pair #define pb push_back #define ppb pop_back #define pf push_front #define ppf pop_front #define all(x) ((x).begin()), ((x).end()) #define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++) #define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--) inline void maxa (ll &a, ll b) { if (a<b) a=b; } inline void mina (ll &a, ll b) { if (a>b) a=b; } #define mxN (100'010ll) #define mxM (50'010ll) #define mxK (100'010ll) #define INF (LLONG_MAX>>3ll) ll n, m, k; vcll ar(mxN); vc<vc<int>> B; vc<vcll> cl_needs(mxN); vc<vcll> pl_needs(mxN); vcll temp_fr(mxK,0); vc<vcll> inds(mxK); inline void clean_dups (vcll &a) { for (ll c:a) temp_fr[c]=1; vcll b; for (ll c:a) if (temp_fr[c]) { b.pb(c); temp_fr[c]=0; } } inline ll modit (ll x) { return ((x%m)+m)%m; } inline void bd_needs() { ll j, c; f0r(j,0,m-1) for (int c:B[j]) cl_needs[c].pb(j+1); f0r(c,0,k) { for (ll i:inds[c]) { for ( ll J:cl_needs[c]) { pl_needs[i].pb(modit(J-i)); // printf("pl %lli, needs %lli\n", i, modit(J-i)); } clean_dups(pl_needs[i]); } cl_needs[c].clear(); } } vcll fr(mxK,0); ll good_cnt; inline void push (ll i) { for (ll r:pl_needs[i]) if (++fr[r]==m) good_cnt++; } inline void pull (ll i) { for (ll r:pl_needs[i]) if (fr[r]--==m) good_cnt--; } vcb can_paint(mxN,0); vcll dp(mxN,INF); inline void slide() { ll i, j; good_cnt=0; f0r(i,1,m) push(i); can_paint[m]=good_cnt; f0r(i,m+1,n) { push(i); pull(i-m); can_paint[i]=good_cnt; } // f0r(i,1,n) printf("can_paint[%lli]: %lli\n", i, (ll)can_paint[i]); } struct MINQ { ll push_time, pop_time; deque<prll> q; inline MINQ() { push_time=0; pop_time=0; while (q.sz()) q.ppb(); q.pb({INF,0}); } inline void push (ll x) { while (q.sz() and x<q.back().fi) q.ppb(); q.pb({x,++push_time}); // printf("pushed {%lli, %lli}\n", x, push_time); } inline void pop () { if (q.sz() and q.front().se == ++pop_time) { // printf("popping {%lli, %lli}\n", q.front().fi, q.front().se); q.ppf(); } } inline ll min() { return q.sz() ? q.front().fi : INF; } } minq; inline void do_dp() { dp[0]=0; ll i; f0r(i,0,m-1) minq.push(dp[i]); // printf("dp[1]: %lli\n", dp[1]); f0r(i,m,n) { /* printf("i: %lli\n", i); if (can_paint[i]) { printf("%lli is good, minq.min(): %lli\n", i, minq.min()); } */ dp[i] = can_paint[i] ? minq.min()+1 : INF; minq.push(dp[i]); // printf("pushinggggggggggggggg\n"); minq.pop(); // printf("poppinnnnnnnnnnnnnnn\n"); } // f0r(i,1,n) printf("dp[%lli]: %lli\n", i, dp[i]); } inline void bd_inds() { ll i; f0r(i,1,n) inds[ar[i]].pb(i); } int minimumInstructions( int N, int M, int K, vc<int> C, vc<int> A, vc<vc<int>> bar) { n=N; m=M; k=K; swap(B,bar); ll i, j; f0r(i,1,n) ar[i]=C[i-1]; // printf("got input\n"); bd_inds(); bd_needs(); // printf("bt needs\n"); slide(); // printf("slided\n"); do_dp(); // printf("done\n"); // printf("n: %lli, dp[n]: %lli\n", n, dp[n]); return dp[n]>=n+10 ? -1 : dp[n]; }
#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...