#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
long long n,d=0,nn=0,a[2][500069],wg[500069],inf=1e18;
struct segtree
{
long long l,r,lz;
pair<long long,long long> mn;
segtree *p[2];
void bd(long long lh,long long rh)
{
l=lh;
r=rh;
lz=0;
if(l==r)
{
mn={wg[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);
}
mn=min(p[0]->mn,p[1]->mn);
}
}
void blc()
{
long long ii;
for(ii=0;ii<2;ii++)
{
p[ii]->mn.fr+=lz;
p[ii]->lz+=lz;
}
lz=0;
}
void ud(long long lh,long long rh,long long w)
{
if(l>rh||r<lh);
else if(l>=lh&&r<=rh)
{
mn.fr+=w;
lz+=w;
}
else
{
long long ii;
blc();
for(ii=0;ii<2;ii++)
{
p[ii]->ud(lh,rh,w);
}
mn=min(p[0]->mn,p[1]->mn);
}
}
pair<long long,long long> qr(long long lh,long long rh)
{
if(l>rh||r<lh)
{
return {inf,-1};
}
else if(l>=lh&&r<=rh)
{
return mn;
}
else
{
blc();
return min(p[0]->qr(lh,rh),p[1]->qr(lh,rh));
}
}
}
sg[2];
int main()
{
long long i,ii,j,k,l,w,ww,z=0;
pair<long long,long long> tmp;
scanf("%lld",&n);
for(i=1;i<=n;i++)
{
for(ii=0;ii<2;ii++)
{
scanf("%lld",&a[ii][i]);
}
}
k=0;
for(i=n;i;i--)
{
k+=a[1][i];
wg[i]=k+inf*!k;
z+=k;
}
d=wg[1];
sg[0].bd(1,n);
k=0;
for(i=1;i<=n;i++)
{
k+=(wg[i]<=0||wg[i]==inf)*2-1;
if(a[0][i])
{
wg[i]=k;
}
else
{
wg[i]=inf;
}
}
sg[1].bd(1,n);
for(;d;)
{
tmp=sg[1].qr(1,n);
k=tmp.sc;
w=tmp.fr;
tmp=sg[0].qr(1,k);
ww=min(min(tmp.fr,a[0][k]),d);
assert(ww);
z+=w*ww;
d-=ww;
a[0][k]-=ww;
if(!a[0][k])
{
sg[1].ud(k,k,inf);
}
sg[0].ud(1,k,-ww);
for(;1;)
{
tmp=sg[0].qr(1,k);
l=tmp.sc;
w=tmp.fr;
if(w)
{
break;
}
sg[1].ud(l,n,2);
sg[0].ud(l,l,inf);
}
}
printf("%lld\n",z);
}
Compilation message
bulves.cpp: In function 'int main()':
bulves.cpp:90:17: warning: unused variable 'j' [-Wunused-variable]
long long i,ii,j,k,l,w,ww,z=0;
^
bulves.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
bulves.cpp:98:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&a[ii][i]);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
2096 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
2096 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
2096 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
2096 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
2096 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
