# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
987167 |
2024-05-22T07:43:44 Z |
Pyqe |
Radio Towers (IOI22_towers) |
C++17 |
|
1031 ms |
171036 KB |
#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long inf=1e18;
long long n,udn=0,a[100069],uds[100069],sp[17][100069],lg2[100069];
multiset<long long> ms;
multiset<pair<long long,pair<long long,long long>>> rg;
bitset<100069> spc;
struct segtree
{
long long l,r,sm;
pair<long long,long long> mxl,mxr;
segtree *p[2];
void bd(long long lb,long long rb)
{
l=lb;
r=rb;
if(l==r)
{
sm=spc[l];
mxl={spc[l],-l};
mxr={spc[l],l};
}
else
{
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);
}
sm=p[0]->sm+p[1]->sm;
mxl=max(p[0]->mxl,p[1]->mxl);
mxr=max(p[0]->mxr,p[1]->mxr);
}
}
void ud(long long x,long long w)
{
if(l>=x&&r<=x)
{
sm+=w;
mxl.fr+=w;
mxr.fr+=w;
}
else
{
long long ii;
for(ii=0;ii<2;ii++)
{
if(!(p[ii]->l>x||p[ii]->r<x))
{
segtree *tmp=p[ii];
p[ii]=new segtree;
*p[ii]=*tmp;
p[ii]->ud(x,w);
}
}
sm=p[0]->sm+p[1]->sm;
mxl=max(p[0]->mxl,p[1]->mxl);
mxr=max(p[0]->mxr,p[1]->mxr);
}
}
long long qrs(long long lb,long long rb)
{
if(l>rb||r<lb)
{
return 0;
}
else if(l>=lb&&r<=rb)
{
return sm;
}
else
{
return p[0]->qrs(lb,rb)+p[1]->qrs(lb,rb);
}
}
pair<long long,long long> qrxl(long long lb,long long rb)
{
if(l>rb||r<lb)
{
return {-inf,-1};
}
else if(l>=lb&&r<=rb)
{
return mxl;
}
else
{
return max(p[0]->qrxl(lb,rb),p[1]->qrxl(lb,rb));
}
}
pair<long long,long long> qrxr(long long lb,long long rb)
{
if(l>rb||r<lb)
{
return {-inf,-1};
}
else if(l>=lb&&r<=rb)
{
return mxr;
}
else
{
return max(p[0]->qrxr(lb,rb),p[1]->qrxr(lb,rb));
}
}
}
sg[100069];
inline void spbd()
{
long long i,j,k;
for(i=1;i<=n;i++)
{
sp[0][i]=a[i];
}
for(i=1;1ll<<i<=n;i++)
{
for(j=1;j<=n-(1ll<<i)+1;j++)
{
sp[i][j]=min(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]++);
}
}
inline long long spqr(long long lb,long long rb)
{
long long e=lg2[rb-lb+1];
return min(sp[e][lb],sp[e][rb-(1ll<<e)+1]);
}
void init(int on,vector<int> aa)
{
long long i,k,l=-1,w,k2,l2;
n=on;
for(i=1;i<=n;i++)
{
a[i]=aa[i-1];
}
ms.insert(-inf);
ms.insert(inf);
for(i=1;i<=n;i++)
{
if(((i==1||a[i]<a[i-1])&&(i==n||a[i]<a[i+1]))||(i>1&&i<n&&a[i]>max(a[i-1],a[i+1])))
{
ms.insert(i);
if(l!=-1)
{
rg.insert({abs(a[l]-a[i]),{l,i}});
}
l=i;
spc[i]=1;
}
}
sg[0].bd(1,n);
for(;!rg.empty();)
{
w=rg.begin()->fr;
k=rg.begin()->sc.fr;
l=rg.begin()->sc.sc;
rg.erase(rg.begin());
if(ms.find(k)==ms.end()||ms.find(l)==ms.end())
{
continue;
}
ms.erase(k);
ms.erase(l);
k2=*prev(ms.lower_bound(k));
l2=*ms.upper_bound(l);
if(k2!=-inf&&l2!=inf)
{
rg.insert({abs(a[k2]-a[l2]),{k2,l2}});
}
udn++;
uds[udn]=w;
sg[udn]=sg[udn-1];
sg[udn].ud(k,-1);
sg[udn].ud(l,-1);
}
spbd();
}
int max_towers(int lb,int rb,int cw)
{
long long k,w,w2,w3,p,mn,z;
pair<long long,long long> tmp;
lb++;
rb++;
p=lower_bound(uds+1,uds+udn+1,cw)-uds-1;
w=sg[p].sm;
w2=sg[p].qrs(1,lb-1);
w3=sg[p].qrs(rb+1,n);
z=(max(w-(w2+1)/2*2-(w3+1)/2*2,0ll)+1)/2;
if(w2%2)
{
tmp=sg[p].qrxl(lb,rb);
if(tmp.fr)
{
k=-tmp.sc;
mn=spqr(lb,k-1);
z+=a[k]-mn>=cw;
}
}
if(w3%2)
{
tmp=sg[p].qrxr(lb,rb);
if(tmp.fr)
{
k=tmp.sc;
mn=spqr(k+1,rb);
z+=a[k]-mn>=cw;
}
}
z=max(z,1ll);
return z;
}
Compilation message
towers.cpp: In function 'void spbd()':
towers.cpp:134:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
134 | sp[i][j]=min(sp[i-1][j],sp[i-1][j+(1ll<<i-1)]);
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
386 ms |
25176 KB |
Output is correct |
2 |
Correct |
817 ms |
37628 KB |
Output is correct |
3 |
Correct |
803 ms |
37808 KB |
Output is correct |
4 |
Correct |
860 ms |
37592 KB |
Output is correct |
5 |
Correct |
790 ms |
37596 KB |
Output is correct |
6 |
Incorrect |
780 ms |
37836 KB |
11314th lines differ - on the 1st token, expected: '1', found: '2' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
7768 KB |
1st lines differ - on the 1st token, expected: '13', found: '15' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
7768 KB |
1st lines differ - on the 1st token, expected: '13', found: '15' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
816 ms |
125088 KB |
1st lines differ - on the 1st token, expected: '11903', found: '11904' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
227 ms |
32892 KB |
Output is correct |
2 |
Correct |
847 ms |
126404 KB |
Output is correct |
3 |
Correct |
770 ms |
126156 KB |
Output is correct |
4 |
Correct |
1004 ms |
171036 KB |
Output is correct |
5 |
Correct |
978 ms |
170632 KB |
Output is correct |
6 |
Correct |
986 ms |
170948 KB |
Output is correct |
7 |
Correct |
1031 ms |
170480 KB |
Output is correct |
8 |
Correct |
555 ms |
37712 KB |
Output is correct |
9 |
Correct |
566 ms |
37720 KB |
Output is correct |
10 |
Correct |
613 ms |
37848 KB |
Output is correct |
11 |
Correct |
623 ms |
37588 KB |
Output is correct |
12 |
Correct |
257 ms |
126404 KB |
Output is correct |
13 |
Correct |
434 ms |
170436 KB |
Output is correct |
14 |
Correct |
446 ms |
170936 KB |
Output is correct |
15 |
Correct |
34 ms |
37584 KB |
Output is correct |
16 |
Correct |
36 ms |
37584 KB |
Output is correct |
17 |
Correct |
286 ms |
122228 KB |
Output is correct |
18 |
Correct |
279 ms |
126420 KB |
Output is correct |
19 |
Correct |
280 ms |
126468 KB |
Output is correct |
20 |
Correct |
457 ms |
170440 KB |
Output is correct |
21 |
Correct |
455 ms |
170752 KB |
Output is correct |
22 |
Correct |
441 ms |
170436 KB |
Output is correct |
23 |
Correct |
487 ms |
170492 KB |
Output is correct |
24 |
Correct |
35 ms |
37680 KB |
Output is correct |
25 |
Correct |
33 ms |
37596 KB |
Output is correct |
26 |
Correct |
33 ms |
37852 KB |
Output is correct |
27 |
Correct |
34 ms |
37584 KB |
Output is correct |
28 |
Correct |
6 ms |
9048 KB |
Output is correct |
29 |
Correct |
8 ms |
9816 KB |
Output is correct |
30 |
Correct |
7 ms |
9836 KB |
Output is correct |
31 |
Correct |
4 ms |
8024 KB |
Output is correct |
32 |
Correct |
4 ms |
8024 KB |
Output is correct |
33 |
Correct |
5 ms |
8280 KB |
Output is correct |
34 |
Correct |
6 ms |
9048 KB |
Output is correct |
35 |
Correct |
7 ms |
9048 KB |
Output is correct |
36 |
Correct |
7 ms |
9816 KB |
Output is correct |
37 |
Correct |
7 ms |
9816 KB |
Output is correct |
38 |
Correct |
7 ms |
9816 KB |
Output is correct |
39 |
Correct |
7 ms |
9816 KB |
Output is correct |
40 |
Correct |
5 ms |
8024 KB |
Output is correct |
41 |
Correct |
5 ms |
8024 KB |
Output is correct |
42 |
Correct |
4 ms |
8024 KB |
Output is correct |
43 |
Correct |
4 ms |
8024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
7768 KB |
1st lines differ - on the 1st token, expected: '13', found: '15' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
386 ms |
25176 KB |
Output is correct |
2 |
Correct |
817 ms |
37628 KB |
Output is correct |
3 |
Correct |
803 ms |
37808 KB |
Output is correct |
4 |
Correct |
860 ms |
37592 KB |
Output is correct |
5 |
Correct |
790 ms |
37596 KB |
Output is correct |
6 |
Incorrect |
780 ms |
37836 KB |
11314th lines differ - on the 1st token, expected: '1', found: '2' |
7 |
Halted |
0 ms |
0 KB |
- |