oj.uz

Submission #401512

# Submission time Handle Problem Language Result Execution time Memory
401512 2021-05-10T12:48:00 Z Pyqe Floppy (RMI20_floppy) C++14
100 / 100
 131 ms 42436 KB 
#include <bits/stdc++.h>
#include "floppy.h"

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n,nn=0,lg2[400069],al[200069][2],dh[200069],peu[200069],sr[200069],pst[200069];
pair<long long,long long> sp[19][400069];
bitset<400069> ba;
pair<long long,bool> sk[200069];

void spbd()
{
	long long i,j,k;
	
	for(i=1;1ll<<i<=n;i++)
	{
		for(j=0;j<n-(1ll<<i)+1;j++)
		{
			sp[i][j]=max(sp[i-1][j],sp[i-1][j+(1ll<<i-1)]);
		}
	}
	for(i=1;i<=n;i++)
	{
		for(k=i;k>1;k/=2,lg2[i]++);
	}
}

long long spqr(long long lh,long long rh)
{
	long long e=lg2[rh-lh+1];
	
	return max(sp[e][lh],sp[e][rh-(1ll<<e)+1]).sc;
}

long long rk(long long lh,long long rh)
{
	long long p=spqr(lh,rh);
	
	if(lh<p)
	{
		al[p][0]=rk(lh,p-1);
	}
	if(p<rh)
	{
		al[p][1]=rk(p+1,rh);
	}
	return p;
}

void trv(long long x)
{
	long long ii,l;
	
	for(ii=0;ii<2;ii++)
	{
		l=al[x][ii];
		ba[n*2+ii]=l>=0;
	}
	n++;
	for(ii=0;ii<2;ii++)
	{
		l=al[x][ii];
		if(l+1)
		{
			trv(l);
		}
	}
}

void bd(long long x)
{
	long long ii,l;
	
	nn++;
	sp[0][nn]={dh[x],x};
	peu[x]=nn;
	for(ii=0;ii<2;ii++)
	{
		l=al[x][ii];
		if(l+1)
		{
			dh[l]=dh[x]+1;
			bd(l);
			nn++;
			sp[0][nn]={dh[x],x};
		}
		if(!ii)
		{
			sr[x]=n;
			pst[n]=x;
			n++;
		}
	}
}

void spbd2()
{
	long long i,j,k;
	
	for(i=1;1ll<<i<=nn;i++)
	{
		for(j=1;j<=nn-(1ll<<i)+1;j++)
		{
			sp[i][j]=min(sp[i-1][j],sp[i-1][j+(1ll<<i-1)]);
		}
	}
	for(i=1;i<=nn;i++)
	{
		for(lg2[i]=0,k=i;k>1;k/=2,lg2[i]++);
	}
}

long long spqr2(long long lh,long long rh)
{
	long long e=lg2[rh-lh+1];
	
	return min(sp[e][lh],sp[e][rh-(1ll<<e)+1]).sc;
}

long long lca(long long x,long long y)
{
	if(peu[x]>peu[y])
	{
		swap(x,y);
	}
	return spqr2(peu[x],peu[y]);
}

void read_array(int sub,const vector<int> &a)
{
	long long i,ii,k;
	string s="";
	
	n=a.size();
	for(i=0;i<n;i++)
	{
		sp[0][i]={a[i],i};
		for(ii=0;ii<2;ii++)
		{
			al[i][ii]=-1;
		}
	}
	spbd();
	k=rk(0,n-1);
	n=0;
	trv(k);
	for(i=0;i<n*2;i++)
	{
		s+=(ba[i]+'0');
	}
	save_to_floppy(s);
}

vector<int> solve_queries(int sub,int on,const string &s,const vector<int> &la,const vector<int> &ra)
{
	long long t,rr,i,ii;
	vector<int> sq;
	
	for(i=0;i<on;i++)
	{
		for(ii=0;ii<2;ii++)
		{
			al[i][ii]=-1;
		}
	}
	n=0;
	for(i=0;i<on;i++)
	{
		if(nn)
		{
			al[sk[nn].fr][sk[nn].sc]=n;
			nn--;
		}
		for(ii=0;ii<2;ii++)
		{
			if(s[n*2+!ii]-'0')
			{
				nn++;
				sk[nn]={n,!ii};
			}
		}
		n++;
	}
	n=0;
	bd(0);
	spbd2();
	t=la.size();
	for(rr=0;rr<t;rr++)
	{
		sq.push_back(sr[lca(pst[la[rr]],pst[ra[rr]])]);
	}
	return sq;
}

Compilation message

floppy.cpp: In function 'void spbd()':
floppy.cpp:23:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   23 |    sp[i][j]=max(sp[i-1][j],sp[i-1][j+(1ll<<i-1)]);
      |                                            ~^~
floppy.cpp: In function 'void spbd2()':
floppy.cpp:108:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  108 |    sp[i][j]=min(sp[i-1][j],sp[i-1][j+(1ll<<i-1)]);
      |                                            ~^~
stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     if (query_answers.size() != M) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1200 KB Output is correct
2 Correct 3 ms 1192 KB Output is correct
3 Correct 3 ms 1204 KB Output is correct
4 Correct 3 ms 1200 KB Output is correct
5 Correct 3 ms 1204 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9824 KB Output is correct
2 Correct 31 ms 9772 KB Output is correct
3 Correct 31 ms 10356 KB Output is correct
4 Correct 33 ms 10052 KB Output is correct
5 Correct 31 ms 9848 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 39932 KB Output is correct
2 Correct 131 ms 39996 KB Output is correct
3 Correct 120 ms 42436 KB Output is correct
4 Correct 125 ms 41468 KB Output is correct
5 Correct 126 ms 40016 KB Output is correct