#include <bits/stdc++.h>
#pragma GCC optimize ("unroll-loops")
using namespace std;
#define mp make_pair
#define fr first
#define sc second
long long n,d=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 md=(l+r)/2;
p[0]=new segtree;
p[0]->bd(l,md);
p[1]=new segtree;
p[1]->bd(md+1,r);
mn=min(p[0]->mn,p[1]->mn);
}
}
void blc()
{
if(lz)
{
p[0]->mn.fr+=lz;
p[0]->lz+=lz;
p[1]->mn.fr+=lz;
p[1]->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
{
blc();
p[0]->ud(lh,rh,w);
p[1]->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,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=k;
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);
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:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
bulves.cpp:94: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 |
Correct |
1 ms |
1152 KB |
Output is correct |
3 |
Correct |
5 ms |
1152 KB |
Output is correct |
4 |
Correct |
60 ms |
14076 KB |
Output is correct |
5 |
Correct |
109 ms |
27768 KB |
Output is correct |
6 |
Correct |
280 ms |
68984 KB |
Output is correct |
7 |
Execution timed out |
1096 ms |
137336 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
1152 KB |
Output is correct |
3 |
Correct |
5 ms |
1152 KB |
Output is correct |
4 |
Correct |
60 ms |
14076 KB |
Output is correct |
5 |
Correct |
109 ms |
27768 KB |
Output is correct |
6 |
Correct |
280 ms |
68984 KB |
Output is correct |
7 |
Execution timed out |
1096 ms |
137336 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
1152 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
640 KB |
Output is correct |
5 |
Correct |
2 ms |
768 KB |
Output is correct |
6 |
Correct |
3 ms |
1152 KB |
Output is correct |
7 |
Correct |
3 ms |
1152 KB |
Output is correct |
8 |
Correct |
3 ms |
1152 KB |
Output is correct |
9 |
Correct |
2 ms |
1152 KB |
Output is correct |
10 |
Correct |
3 ms |
1152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
1152 KB |
Output is correct |
3 |
Correct |
5 ms |
1152 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
768 KB |
Output is correct |
7 |
Correct |
3 ms |
1152 KB |
Output is correct |
8 |
Correct |
3 ms |
1152 KB |
Output is correct |
9 |
Correct |
3 ms |
1152 KB |
Output is correct |
10 |
Correct |
2 ms |
1152 KB |
Output is correct |
11 |
Correct |
3 ms |
896 KB |
Output is correct |
12 |
Correct |
4 ms |
1152 KB |
Output is correct |
13 |
Correct |
4 ms |
1152 KB |
Output is correct |
14 |
Correct |
4 ms |
1152 KB |
Output is correct |
15 |
Correct |
2 ms |
1152 KB |
Output is correct |
16 |
Correct |
3 ms |
1152 KB |
Output is correct |
17 |
Correct |
5 ms |
1152 KB |
Output is correct |
18 |
Correct |
3 ms |
1152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
1152 KB |
Output is correct |
3 |
Correct |
5 ms |
1152 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
768 KB |
Output is correct |
7 |
Correct |
3 ms |
1152 KB |
Output is correct |
8 |
Correct |
3 ms |
1152 KB |
Output is correct |
9 |
Correct |
3 ms |
1152 KB |
Output is correct |
10 |
Correct |
2 ms |
1152 KB |
Output is correct |
11 |
Correct |
60 ms |
14076 KB |
Output is correct |
12 |
Correct |
109 ms |
27768 KB |
Output is correct |
13 |
Correct |
280 ms |
68984 KB |
Output is correct |
14 |
Execution timed out |
1096 ms |
137336 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |