Submission #764665

#	Time	Username	Problem	Language	Result	Execution time	Memory
764665		raysh07	Painting Walls (APIO20_paint)	C++17	100 / 100	1245 ms	15864 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 69;
int seg[4 * N];

void upd(int l, int r, int pos, int qp, int v){
    if (l == r){
        seg[pos] = v;
        return;
    }
    
    int mid = (l + r)/2;
    if (qp <= mid) upd(l, mid, pos*2, qp, v);
    else upd(mid + 1, r, pos*2 + 1, qp, v);
    
    seg[pos] = min(seg[pos * 2], seg[pos * 2 + 1]);
}

int query(int l, int r, int pos, int ql, int qr){
    if (l >= ql && r <= qr) return seg[pos];
    else if (l > qr || r < ql) return 1e8;
    
    int mid = (l + r)/2;
    return min(query(l, mid, pos*2, ql, qr), query(mid + 1, r, pos*2 + 1, ql, qr));
}

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
    vector<vector<int>> adj(k);
    for (int i = 0; i < m; i++){
        for (auto x : b[i]){
            adj[x].push_back(i);
        }
    }
    
    //adj[x] size is atmost sqrt(4e5) = 650 
    vector<bool> can(n + 1, false);
    vector <int> mp(m, 0);
    for (int i = 0; i < n; i++){
        //if painter x can do y, then increase frequency of x - y mod m ofc 
        //then a thing can be done if and only if frequency = m 
        int y = c[i];
        
        if (i >= m){
            for (auto x : adj[c[i - m]]){
                
                int lol = (x - i) % m;
                lol = (lol + m) % m;
                
              //  cout << "SUB " << i - m << " " << " COLOUR " << c[i - m] << " PAINTER " << x << " DIFF " << lol << "\n";
                mp[lol]--;
            }
        }
        
        for (auto x : adj[y]){
            int lol = (x - i) % m;
            lol = (lol + m) % m;
            
          //  cout << "ADD " << i << " " << " COLOUR " << y << " PAINTER " << x << " DIFF " << lol << "\n";
            mp[lol]++;
            if (mp[lol] == m) {
              //  cout << "NOOOO\n";
                can[i + 1] = true;
            }
        }
    }
    
    vector <int> dp(n + 1, 1e8);
    dp[0] = 0;
    
    for (int i = 0; i <= n; i++) upd(0, n, 1, i, dp[i]);
    
    for (int i = 1; i <= n; i++){
        if (can[i]){
            dp[i] = min(dp[i], 1 + query(0, n, 1, i - m, i - 1));
        }
        
        upd(0, n, 1, i, dp[i]);
    }
    
    if (dp[n] > n) return -1;
    else return dp[n];
}

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