#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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
