oj.uz

Submission #70403

# Submission time Handle Problem Language Result Execution time Memory
70403 2018-08-22T19:40:08 Z khohko popa (BOI18_popa) C++17
61 / 100
 210 ms 5096 KB 
#include <bits/stdc++.h>
#ifndef KHOKHO
#include "popa.h"
#endif // KHOKHO
#pragma GCC optimize("O3")
using namespace std;
#define ll int
#define pb push_back
#define fr first
#define sc second
#define MAX ((ll)(1e12+100))
#define MX ((ll)(1e6+100))
#define ARRS ((ll)(2e6+100))
#define HS ((ll)(233))
#define MOD ((ll)(1e9+7))
#define EP ((double)(1e-9))
#define LG 21
#define mul(a,b) a=((a)*(b))%MOD
using namespace std;
 
#ifdef KHOKHO
	ll aa[ARRS];
	ll qr=0;
	int query(int a, int b, int c, int d){
		ll x=0,y=0;
		qr++;
		for(int i=a; i<=b; i++)x=__gcd(x,aa[i]);
		for(int i=c; i<=d; i++)y=__gcd(y,aa[i]);
		return x==y;
	}
#endif
ll l[ARRS];
ll r[ARRS];
 
ll dp[1100][1100];
 
 
ll slv(ll i,ll j){
	if(i==j)dp[i][j]=-1;
	if(dp[i][j])return dp[i][j];
	for(int k=i; k<j; k++){
		if(l[k]<=i&&j-1<=r[k]&&slv(i,k)&&slv(k+1,j)){
			return dp[i][j]=k+1;
		}
	}
	return 0;
}
 
ll bld(ll l,ll r,int *lt,int *rt){
	slv(l,r);
	ll x=dp[l][r]-1;
	if(x==-2)return -1;
	if(x==-1)return -1;
	//cout<<l<<" "<<r<<" "<<x<<endl;
	lt[x]=bld(l,x,lt,rt);
	rt[x]=bld(x+1,r,lt,rt);
	return x;
}
 
 
int solve(int n, int* lt, int* rt){
	for(int i=0; i<n; i++){
		l[i]=i;
		while(l[i]&&query(l[l[i]-1],i,i,i))
			l[i]=l[l[i]-1];
	}
 
	for(int i=n-1; i>=0; i--){
		r[i]=i;
		while(r[i]<n-1&&query(i,r[r[i]+1],i,i))
			r[i]=r[r[i]+1];
	}
	for(int i=0; i<=n; i++)
		for(int j=0; j<=n; j++)
			dp[i][j]=0;
 
//
//	for(int d=0; d<=n; d++){
//		for(int i=0; i<=n-d; i++){
//			ll j=i+d;
//			if(i==j){dp[i][j]=-1;continue;}
//			for(int k=i; k<j; k++){
//				if(dp[i][k]&&dp[k+1][j]&&l[k]<=i&&j-1<=r[k])
//					{dp[i][j]=k+1;break;}
//			}
//		}
//	}
	//slv(0,n);
 
	return bld(0,n,lt,rt);
}

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 760 KB Output is correct
2 Correct 21 ms 820 KB Output is correct
3 Correct 11 ms 852 KB Output is correct
4 Correct 23 ms 972 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 4972 KB Output is correct
2 Correct 195 ms 5096 KB Output is correct
3 Correct 64 ms 5096 KB Output is correct
4 Correct 210 ms 5096 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 5096 KB too many queries
2 Halted 0 ms 0 KB -