Submission #917221

#	Time	Username	Problem	Language	Result	Execution time	Memory
917221		coding_snorlax	Painting Walls (APIO20_paint)	C++14	63 / 100	1566 ms	14120 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
int tr[1<<18]={0},n=100005;
vector<int> color[100002],possible1;
int Total[100002]={0};
int possible_place[100002]={0};
void modify(int p, int x) {
    for(tr[p+=n] = x; p > 1; p>>=1)
        tr[p>>1] = max(tr[p],tr[p^1]);
}
int query(int l, int r) { // [l,r)
    int res = -1e9;
    for(l+=n,r+=n; l<r; l>>=1,r>>=1) {
        if(l&1) res = max(res, tr[l++]);
        if(r&1) res = max(res, tr[--r]);
    }
    return res;
}
int cal_answer(int M,vector<int> possible){
    if(!possible[M-1]) return -1;
    int bound = M-1,answer = 1;
    while(bound<(int)possible.size()-1){
        int flag = 0;
        for(int i=bound+M;i>bound;i--){
            if(possible[i]){bound = i;answer +=1;flag = 1;break;}
        }
        if(!flag){answer = -1;break;}
    }
    return answer;
}
int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) {
   for(int i=0;i<(int)B.size();i++){
      for(int j=0;j<(int)B[i].size();j++){
        color[B[i][j]].push_back(i);
      }
   }
   for(int i=0;i<N;i++){
        for(int j:color[C[i]]){
            int active = (j + M - (i%M))%M;
            Total[active]++;
            modify(active+1,Total[active]);
        }
        if(i>=M){
            for(int j:color[C[i-M]]){
                int active = (j + M - (i%M))%M;
                Total[active]--;
                modify(active+1,Total[active]);
            }
        }
        if(query(1,100001)==M) possible_place[i]=1;
   }
   for(int i=0;i<N;i++) possible1.push_back(possible_place[i]);
   return cal_answer(M,possible1);
}

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