Submission #70168

#	Time	Username	Problem	Language	Result	Execution time	Memory
70168		khohko	popa (BOI18_popa)	C++17	0 / 100	22 ms	464 KiB

popa

#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 f[ARRS];
ll pr[ARRS];

ll dp[1100][1100];
bitset<1100> ps[1100];
bitset<1100> psl[1100];
bitset<1100> tb;

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){
	stack<ll> sk;
	for(int i=0; i<n; i++)lt[i]=rt[i]=-1;
	ll rut=-1;
	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];
		//cout<<qr<<endl;
		if(rut==-1||l[i]<=rut){
			lt[i]=rut;
			//pr[rut]=i;
			rut=i;
		}
		else if(l[i]==i){
			rt[i-1]=i;
			pr[i]=i-1;
		}
		else {
			ll x=l[i];
			while(f[x])x++;
			ll p=pr[x];
			rt[p]=i;
			lt[i]=x;
			for(int j=x; j<i; j++)f[j]=1;
		}
	}
	return rut;
}

#ifdef KHOKHO
int pa[ARRS];
int pb[ARRS];

int main(){
	#ifdef KHOKHO
		freopen("in.in","r",stdin);
		freopen("out.out","w",stdout);
	#endif // KHOKHO
	//ios::sync_with_stdio(0);

	ll n;
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>aa[i];
	}
	ll rt=solve(n,pa,pb);
	cout<<rt<<endl;
	for(int i=0; i<n; i++){
		cout<<pa[i]<<" ";
	}
	cout<<endl;
	for(int i=0; i<n; i++){
		cout<<pb[i]<<" ";
	}
	cout<<endl;
	cout<<endl;
	cout<<"asked:"<<qr<<endl;

}
#endif

• Subtask 1: 0 / 37
• Subtask 2: 0 / 24
• Subtask 3: 0 / 39