Submission #645508

#	Time	Username	Problem	Language	Result	Execution time	Memory
645508		Tenis0206	Painting Walls (APIO20_paint)	C++11	100 / 100	417 ms	255684 KiB

paint

#include <bits/stdc++.h>

#include "paint.h"

using namespace std;

const int oo = INT_MAX;

vector<int> dp[100005];
vector<int> l[100005];

int lmax[100005],dp_rez[100005];

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b)
{
    for(int i=0; i<m; i++)
    {
        for(auto it : b[i])
        {
            l[it].push_back(i);
        }
    }
    dp[0].resize(l[c[0]].size());
    for(int j=0; j<l[c[0]].size(); j++)
    {
        dp[0][j] = 1;
    }
    lmax[0] = 1;
    for(int i=1; i<n; i++)
    {
        dp[i].resize(l[c[i]].size());
        int p = 0;
        for(int j=0; j<l[c[i]].size(); j++)
        {
            dp[i][j] = 1;
            if(l[c[i]][j]!=0)
            {
                while(p<l[c[i-1]].size() && l[c[i-1]][p] < l[c[i]][j]-1)
                {
                    ++p;
                }
                if(p<l[c[i-1]].size() && l[c[i-1]][p]==l[c[i]][j]-1)
                {
                    dp[i][j] = max(dp[i][j],dp[i-1][p] + 1);
                }
            }
            else
            {
                if(!l[c[i-1]].empty() && l[c[i-1]].back()==m-1)
                {
                    dp[i][j] = max(dp[i][j], 1 + dp[i-1][l[c[i-1]].size()-1]);
                }
            }
            lmax[i] = max(lmax[i],dp[i][j]);
        }
    }
    deque<int> q;
    for(int i=0; i<n; i++)
    {
        if(lmax[i] < m)
        {
            dp_rez[i] = oo;
            while(!q.empty() && dp_rez[q.back()] > dp_rez[i])
            {
                q.pop_back();
            }
            q.push_back(i);
            continue;
        }
        while(!q.empty() && q.front() < i - m)
        {
            q.pop_front();
        }
        if(i < m)
        {
            dp_rez[i] = 1;
        }
        else
        {
            int val = dp_rez[q.front()];
            if(val == oo)
            {
                dp_rez[i] = oo;
            }
            else
            {
                dp_rez[i] = 1 + val;
            }
        }
        while(!q.empty() && dp_rez[q.back()] > dp_rez[i])
        {
            q.pop_back();
        }
        q.push_back(i);
    }
    if(dp_rez[n-1]==oo)
    {
        dp_rez[n-1] = -1;
    }
    return dp_rez[n-1];
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int j=0; j<l[c[0]].size(); j++)
      |                  ~^~~~~~~~~~~~~~~
paint.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int j=0; j<l[c[i]].size(); j++)
      |                      ~^~~~~~~~~~~~~~~
paint.cpp:38:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |                 while(p<l[c[i-1]].size() && l[c[i-1]][p] < l[c[i]][j]-1)
      |                       ~^~~~~~~~~~~~~~~~~
paint.cpp:42:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                 if(p<l[c[i-1]].size() && l[c[i-1]][p]==l[c[i]][j]-1)
      |                    ~^~~~~~~~~~~~~~~~~

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