Submission #718672

#	Time	Username	Problem	Language	Result	Execution time	Memory
718672		MDSPro	Painting Walls (APIO20_paint)	C++17	51 / 100	1153 ms	524288 KiB

paint

#include "paint.h"
 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
 
const int INF = 1e9;
struct SegTree {
    int n,N;
    vector<int> tr;
 
    SegTree(int sz):n(sz){
        N = (1<<(32-__builtin_clz(n)));
        tr.assign(2*N,INF);
    }
 
    void upd(int idx, int val){
        for(idx += N, tr[idx] = val, idx >>= 1; idx > 0; idx >>= 1) tr[idx] = min(tr[idx<<1],tr[idx<<1|1]);
    }
 
    int get(int l, int r){
        int ans = INF;
        for(l += N, r += N; l < r; l >>= 1, r >>= 1){
            if(l&1) ans = min(tr[l++],ans);
            if(r&1) ans = min(ans,tr[--r]);
        }
 
        return ans;
    }
};
 
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
    // [y,y+M-1]
    vector<vector<int>> contractors(K,vector<int>(0));
    for(int i = 0; i < M; ++i){
        for(int j = 0; j < A[i]; ++j){
            contractors[B[i][j]].emplace_back(i);
        }
    }
    //  M = 3 
    // [1 0 1]
    // [1 1 1]
    // [1 1 0]
    // [0 0 1] N-M = 3
    // [1 1 0]
    // [0 1 1]
    
    // TR
    // xy..y.x.y.....y....xy.x.x.y.x.x..y..xy..........
    // 
    vector<vector<int>> dp1(N, vector<int>(M,0));
    vector<pair<int,int>> segs;
    for(int y = N-1; y >= 0; --y){
        for(int x: contractors[C[y]]){
            if(y == N-1) dp1[y][x] = 1;
            else dp1[y][x] = dp1[y+1][(x+1)%M]+1;
 
            if(y <= N-M && dp1[y][x] >= M) segs.emplace_back(y,y+M-1);
        }
    }
 
    sort(segs.begin(),segs.end());
 
    SegTree sg(N);
    vector<int> dp(N,INF);
    for(auto z: segs){
        int l = z.first, r = z.second;
        if(l == 0) dp[r] = 1;
        else dp[r] = min(sg.get(l-1,r)+1,dp[r]);
        sg.upd(r,dp[r]);
    }
 
    if(dp[N-1] == INF) return -1;
    else return dp[N-1];
};
 
 
// O(N*M*logC+N*logN)

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