Submission #576568

#	Time	Username	Problem	Language	Result	Execution time	Memory
576568		ParsaEs	Painting Walls (APIO20_paint)	C++14	100 / 100	1055 ms	13008 KiB

paint

//InTheNameOfGOD
//PRS;)
#include<bits/stdc++.h>
#include "paint.h"
#define rep(i, l, r) for(ll i = l; i < r; i++)
#define pb push_back
#define X first
#define Y second
typedef int ll;
using namespace std;
typedef pair<ll, ll> pi;
constexpr ll inf = 1e9;
ll minimumInstructions(ll N, ll M, ll K, vector<ll> C, vector<ll> A, vector<vector<ll>> B)
{
    vector<ll> c[K + 1];
    rep(i, 0, B.size()) for(ll j : B[i]) c[j].pb(i);
    vector<ll> dp(N + 1, inf), cnt(M + 1, 0);
    deque<pi> q;
    ll gn = 0;
    rep(i, 0, N)
    {
        if(M <= i) for(ll j : c[C[i - M]]) gn -= (cnt[(N + j - i) % M]-- == M);
        for(ll j : c[C[i]]) gn += (++cnt[(N + j - i) % M] == M);
        if(gn)
        {
            if(i == M - 1) dp[i] = 1;
            else
            {
                while(!q.empty() && q.front().Y < i - M) q.pop_front();
                if(!q.empty()) dp[i] = q.front().X + 1;
            }
            while(!q.empty() && q.back().X >= dp[i]) q.pop_back();
            q.pb({dp[i], i});
        }
    }
    return (dp[N - 1] >= inf ? -1 : dp[N - 1]);
}

Compilation message (stderr)

paint.cpp: In function 'll minimumInstructions(ll, ll, ll, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:5:38: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i, l, r) for(ll i = l; i < r; i++)
......
   16 |     rep(i, 0, B.size()) for(ll j : B[i]) c[j].pb(i);
      |         ~~~~~~~~~~~~~~                
paint.cpp:16:5: note: in expansion of macro 'rep'
   16 |     rep(i, 0, B.size()) for(ll j : B[i]) c[j].pb(i);
      |     ^~~

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 37 / 37