oj.uz

Submission #737799

# Submission time Handle Problem Language Result Execution time Memory
737799 2023-05-07T18:14:52 Z shadow_sami Painting Walls (APIO20_paint) C++17
0 / 100
 18 ms 31840 KB 
#include "paint.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 2e3+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;
vi color[mx];
ll possible[mx][mx];
ll dp[mx];
vector<pi> v;

ll calc(ll a){
	return ((a + m - 1) % m);
}

typedef struct SEGMENT_TREE{
	vi arr;
	ll range;
	void init(ll k){
		range = log2(k);
		range = 1 << (range + 3);
		arr.resize(range,1e18);
		return ;
	}
	ll construct(ll ptr,ll l,ll r){
		if(l==r){
			arr[ptr] = 1e18;
			return arr[ptr];
		}
		ll mid = l + (r-l)/2;
		arr[ptr] = min(construct(2*ptr,l,mid),construct(2*ptr+1,mid+1,r));
		return arr[ptr];
	}
	ll query(ll ptr,ll l,ll r,ll st,ll en){
		if(l>en || r<st)
			return 1e18;
		if(l>=st && r<=en)
			return arr[ptr];
		ll mid = l + (r-l)/2;
		return min(query(2*ptr,l,mid,st,en),query(2*ptr+1,mid+1,r,st,en));
	}
	ll update(ll ptr,ll l,ll r,ll value,ll pos){
		if(l==r && l==pos){
			arr[ptr] = value;
			return arr[ptr];
		}			
		if(l>pos || r<pos)
			return arr[ptr];
		ll mid = l + (r-l)/2;
		arr[ptr] = min(update(2*ptr,l,mid,value,pos),update(2*ptr+1,mid+1,r,value,pos));
		return arr[ptr];
	}
}SGT;

SGT sgt;

int minimumInstructions(int N, int M, int K,vector<int> C,vector<int> A,vector<vector<int>> B) {

	n = N,m = M,tp = K;
	fip(0,m){
		fx(B[i]){
			color[x].push_back(i);
		}
	}
	memset(possible,0,sizeof(possible));
	fip(0,n){
		fx(color[C[i]]){
			if(i==0)
				possible[i][x] = 1;
			else
				possible[i][x] = possible[i-1][calc(x)] + 1;
			// debug(i);
			// debug(x);
			// debug(possible[i][x]);
			if(possible[i][x]>=m && i-m+1>=0)
				v.push_back({i-m+1,i});
		}
	}
	fip(0,n+1){
		dp[i] = 1e18;
	}
	srt(v);
	// debug(v);
	sgt.init(n);
	sgt.construct(1,0,n-1);
	fx(v){
		ll l = x.ff;
		ll r = x.ss;
		if(l==0)
			dp[r] = 1;
		else
			dp[r] = min(dp[r],sgt.query(1,0,n-1,l-1,r)+1);
		sgt.update(1,0,n-1,dp[r],r);
	}
	if(dp[n-1]>n)
		return -1;
	else return dp[n-1];
}


// int main(){
//     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//     #ifndef ONLINE_JUDGE
//         freopen("input1.txt", "r", stdin);
//         freopen("output1.txt", "w", stdout);
//         freopen("error1.txt", "w", stderr);
//     #endif // ONLINE_JUDGE

//         int N,M,K;
//         cin>>N>>M>>K;
//         vector<int> C,A;
//         vector<vector<int>> B(M);        
//         fip(0,N){
//         	cin>>tp;
//         	C.push_back(tp);
//         }
//         fip(0,M){
//         	cin>>tp;
//         	A.push_back(tp);
//         	cin>>tp;
//         	// debug(tp);
//         	fjp(0,tp){
//         		cin>>tp2;
//         		// debug(tp2);
//         		B[i].push_back(tp2);
//         		// debug(B[i]);
//         	}
//         }
//         cout<<minimumInstructions(N,M,K,C,A,B);

        
//     cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
//     return 0;
// }

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31828 KB Output is correct
2 Correct 15 ms 31828 KB Output is correct
3 Correct 18 ms 31792 KB Output is correct
4 Correct 15 ms 31712 KB Output is correct
5 Correct 13 ms 31748 KB Output is correct
6 Correct 14 ms 31748 KB Output is correct
7 Correct 17 ms 31804 KB Output is correct
8 Correct 15 ms 31828 KB Output is correct
9 Correct 14 ms 31776 KB Output is correct
10 Correct 15 ms 31760 KB Output is correct
11 Correct 18 ms 31768 KB Output is correct
12 Correct 14 ms 31840 KB Output is correct
13 Runtime error 1 ms 596 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31828 KB Output is correct
2 Correct 15 ms 31828 KB Output is correct
3 Correct 18 ms 31792 KB Output is correct
4 Correct 15 ms 31712 KB Output is correct
5 Correct 13 ms 31748 KB Output is correct
6 Correct 14 ms 31748 KB Output is correct
7 Correct 17 ms 31804 KB Output is correct
8 Correct 15 ms 31828 KB Output is correct
9 Correct 14 ms 31776 KB Output is correct
10 Correct 15 ms 31760 KB Output is correct
11 Correct 18 ms 31768 KB Output is correct
12 Correct 14 ms 31840 KB Output is correct
13 Runtime error 1 ms 596 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31828 KB Output is correct
2 Correct 15 ms 31828 KB Output is correct
3 Correct 18 ms 31792 KB Output is correct
4 Correct 15 ms 31712 KB Output is correct
5 Correct 13 ms 31748 KB Output is correct
6 Correct 14 ms 31748 KB Output is correct
7 Correct 17 ms 31804 KB Output is correct
8 Correct 15 ms 31828 KB Output is correct
9 Correct 14 ms 31776 KB Output is correct
10 Correct 15 ms 31760 KB Output is correct
11 Correct 18 ms 31768 KB Output is correct
12 Correct 14 ms 31840 KB Output is correct
13 Runtime error 1 ms 596 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31828 KB Output is correct
2 Correct 15 ms 31828 KB Output is correct
3 Correct 18 ms 31792 KB Output is correct
4 Correct 15 ms 31712 KB Output is correct
5 Correct 13 ms 31748 KB Output is correct
6 Correct 14 ms 31748 KB Output is correct
7 Correct 17 ms 31804 KB Output is correct
8 Correct 15 ms 31828 KB Output is correct
9 Correct 14 ms 31776 KB Output is correct
10 Correct 15 ms 31760 KB Output is correct
11 Correct 18 ms 31768 KB Output is correct
12 Correct 14 ms 31840 KB Output is correct
13 Runtime error 1 ms 596 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31828 KB Output is correct
2 Correct 15 ms 31828 KB Output is correct
3 Correct 18 ms 31792 KB Output is correct
4 Correct 15 ms 31712 KB Output is correct
5 Correct 13 ms 31748 KB Output is correct
6 Correct 14 ms 31748 KB Output is correct
7 Correct 17 ms 31804 KB Output is correct
8 Correct 15 ms 31828 KB Output is correct
9 Correct 14 ms 31776 KB Output is correct
10 Correct 15 ms 31760 KB Output is correct
11 Correct 18 ms 31768 KB Output is correct
12 Correct 14 ms 31840 KB Output is correct
13 Runtime error 1 ms 596 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -