| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 693062 |
2023-02-02T10:32:33 Z |
Pyqe |
Radio Towers (IOI22_towers) |
C++17 |
|
1651 ms |
396048 KB |
#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long mm=17,ma=1e9,inf=1e18;
long long n,nn=0,rt,a[100069],sk[100069],sk2[100069],al[100069][2],sbt[100069],dh[100069],an[100069],pr[100069],peu[100069],wg[3][100069],bl[100069][mm];
vector<long long> al2[100069];
pair<long long,long long> as[3][100069];
struct segtree
{
long long l,r,sm;
segtree *p[2];
void bd(long long lh,long long rh)
{
l=lh;
r=rh;
sm=0;
if(l<r)
{
long long ii,md=(l+r)/2;
for(ii=0;ii<2;ii++)
{
p[ii]=new segtree;
p[ii]->bd(!ii?l:md+1,!ii?md:r);
}
}
}
void ud(long long x,long long w)
{
if(l>=x&&r<=x)
{
sm+=w;
}
else
{
long long ii;
segtree *tmp;
for(ii=0;ii<2;ii++)
{
if(!(p[ii]->l>x||p[ii]->r<x))
{
tmp=p[ii];
p[ii]=new segtree;
*p[ii]=*tmp;
p[ii]->ud(x,w);
}
}
sm=p[0]->sm+p[1]->sm;
}
}
long long qr(long long lh,long long rh)
{
if(l>rh||r<lh)
{
return 0;
}
else if(l>=lh&&r<=rh)
{
return sm;
}
else
{
return p[0]->qr(lh,rh)+p[1]->qr(lh,rh);
}
}
}
sg[4][100069];
void bd(long long x)
{
long long i,ii,l,e;
pair<long long,long long> mxe={-inf,-1};
sbt[x]=1;
an[x]=x;
for(ii=0;ii<2;ii++)
{
l=al[x][ii];
if(l)
{
dh[l]=dh[x]+1;
pr[l]=x;
bd(l);
sbt[x]+=sbt[l];
al2[x].push_back(l);
mxe=max(mxe,{sbt[l],al2[x].size()-1});
}
}
e=mxe.sc;
if(e!=-1)
{
swap(al2[x][0],al2[x][e]);
}
bl[x][0]=pr[x];
for(i=1;i<=mm;i++)
{
bl[x][i]=bl[bl[x][i-1]][i-1];
}
}
void bd2(long long x)
{
long long i,sz=al2[x].size(),l;
if(sz)
{
an[al2[x][0]]=an[x];
}
n++;
peu[x]=n;
for(i=0;i<sz;i++)
{
l=al2[x][i];
bd2(l);
}
}
void init(int on,vector<int> aa)
{
long long i,ii,u,k,l;
n=on;
for(i=1;i<=n;i++)
{
a[i]=aa[i-1];
l=-1;
for(;nn&&a[sk[nn]]>a[i];nn--)
{
l=sk[nn];
}
if(l!=-1)
{
al[i][0]=l;
}
if(nn)
{
al[sk[nn]][1]=i;
}
nn++;
sk[nn]=i;
}
rt=sk[1];
bd(rt);
n=0;
bd2(rt);
for(ii=0;ii<2;ii++)
{
u=!ii*2-1;
nn=0;
sk2[0]=ma;
for(i=1+(n-1)*ii;i&&i<=n;i+=u)
{
for(;nn&&a[sk[nn]]>a[i];nn--)
{
sk2[nn-1]=max(sk2[nn-1],sk2[nn]);
}
wg[ii][i]=max(sk2[nn]-a[i],0ll);
nn++;
sk[nn]=i;
sk2[nn]=a[i];
}
}
for(i=1;i<=n;i++)
{
wg[2][i]=min(wg[0][i],wg[1][i]);
}
for(ii=0;ii<3;ii++)
{
for(i=1;i<=n;i++)
{
as[ii][i]={wg[ii][i],i};
}
sort(as[ii]+1,as[ii]+n+1);
sg[ii][0].bd(1,n);
for(i=1;i<=n;i++)
{
k=as[ii][i].sc;
sg[ii][i]=sg[ii][i-1];
sg[ii][i].ud(peu[k],1);
}
}
sg[3][0].bd(1,n);
for(i=1;i<=n;i++)
{
k=as[2][i].sc;
sg[3][i]=sg[3][i-1];
sg[3][i].ud(k,1);
}
}
long long qr2(long long xx,long long lh,long long rh,long long cw)
{
return sg[xx][cw].qr(lh,rh);
}
long long pth(long long x,long long xx,long long lh,long long rh,long long cw,bool kd)
{
long long i,p,z=0;
for(;1;x=pr[an[x]])
{
if(pr[an[x]]<lh||pr[an[x]]>rh)
{
break;
}
z+=sg[xx][cw].qr(peu[an[x]],peu[x]);
}
p=x;
for(i=mm-1;i>=0;i--)
{
if(bl[p][i]>=lh&&bl[p][i]<=rh)
{
p=bl[p][i];
}
}
z+=sg[xx][cw].qr(peu[p]+!kd,peu[x]);
return z;
}
int max_towers(int lb,int rb,int cw)
{
long long ii,p[3],z;
lb++;
rb++;
z=rb-lb+1;
for(ii=0;ii<3;ii++)
{
p[ii]=lower_bound(as[ii]+1,as[ii]+n+1,mp((long long)cw,-inf))-as[ii]-1;
}
z-=qr2(3,lb,rb,p[2]);
z+=pth(lb,2,lb,rb,p[2],1);
z-=pth(lb,1,lb,rb,p[1],0);
z+=pth(rb,2,lb,rb,p[2],0);
z-=pth(rb,0,lb,rb,p[0],0);
return z;
}
Compilation message
towers.cpp: In function 'void bd(long long int)':
towers.cpp:106:11: warning: iteration 16 invokes undefined behavior [-Waggressive-loop-optimizations]
106 | bl[x][i]=bl[bl[x][i-1]][i-1];
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
towers.cpp:104:11: note: within this loop
104 | for(i=1;i<=mm;i++)
| ~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
892 ms |
237128 KB |
12th lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3792 KB |
1st lines differ - on the 1st token, expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3792 KB |
1st lines differ - on the 1st token, expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1651 ms |
396048 KB |
2nd lines differ - on the 1st token, expected: '4770', found: '4771' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
617 ms |
88116 KB |
2257th lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3792 KB |
1st lines differ - on the 1st token, expected: '13', found: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
892 ms |
237128 KB |
12th lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
