Submission #293659

#	Time	Username	Problem	Language	Result	Execution time	Memory
293659		errorgorn	Painting Walls (APIO20_paint)	C++14	100 / 100	1192 ms	418168 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

struct node{
	int s,e,m;
	int val=1e9;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int k){
		val=min(val,k);
		if (s==e) return;
		else if (i<=m) l->update(i,k);
		else r->update(i,k);
	}
	
	int query(int i,int j){
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return min(l->query(i,m),r->query(m+1,j));
	}
} *root=new node(0,100005);

int n,m;
vector<int> arr;
vector<int> worker[100005];
vector<int> col[100005];

int nums[50005];
int good=0;

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
	
	n=N,m=M;
	arr=C;
	
	rep(x,0,m){
		for (auto &it:B[x]) col[it].push_back(x);	
	}
	
	rep(x,0,n){
		for (auto &it:col[arr[x]]) worker[x].push_back((x-it+m)%m);	
		
		//for (auto &it:worker[x]) cout<<it<<" "; cout<<endl;
	}
	
	root->update(0,0);
	
	rep(x,0,n){
		for (auto &it:worker[x]){
			nums[it]++;
			if (nums[it]==m) good++;
		}
		
		if (good){
			//cout<<x<<endl;
			root->update(x+1,root->query(x-m+1,x)+1);
		}
		
		if (x-m+1>=0) for (auto &it:worker[x-m+1]){
			if (nums[it]==m) good--;
			nums[it]--;
		}
	}
	
	int ans=root->query(n,n);
	
	if (ans>=1e9) return -1;
	else return ans;
}

Compilation message (stderr)

paint.cpp: In constructor 'node::node(int, int)':
paint.cpp:31:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

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