#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
int n,a[2][500069];
long long d=0,wg[500069],inf=1e18;
struct segtree
{
int l,r;
pair<long long,int> mn;
long long lz;
segtree *p[2];
void bd(int lh,int rh)
{
l=lh;
r=rh;
lz=0;
if(l==r)
{
mn={wg[l],l};
}
else
{
int 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);
}
}
inline 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(int lh,int 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,int> qr(int lh,int 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()
{
int i,ii,k,l,ww;
long long w,z=0;
pair<long long,int> tmp;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(ii=0;ii<2;ii++)
{
scanf("%d",&a[ii][i]);
}
k=min(a[0][i],a[1][i]);
for(ii=0;ii<2;ii++)
{
a[ii][i]-=k;
}
}
w=0;
for(i=n;i;i--)
{
w+=a[1][i];
wg[i]=w+inf*!w;
z+=w;
}
d=w;
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;)
{
k=sg[1].mn.sc;
w=sg[1].mn.fr;
tmp=sg[0].qr(1,k);
ww=min(min(tmp.fr,(long long)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:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
bulves.cpp:96:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[ii][i]);
~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
1152 KB |
Output is correct |
3 |
Correct |
5 ms |
1152 KB |
Output is correct |
4 |
Correct |
59 ms |
13688 KB |
Output is correct |
5 |
Correct |
112 ms |
27000 KB |
Output is correct |
6 |
Correct |
185 ms |
66812 KB |
Output is correct |
7 |
Execution timed out |
1004 ms |
133572 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
1152 KB |
Output is correct |
3 |
Correct |
5 ms |
1152 KB |
Output is correct |
4 |
Correct |
59 ms |
13688 KB |
Output is correct |
5 |
Correct |
112 ms |
27000 KB |
Output is correct |
6 |
Correct |
185 ms |
66812 KB |
Output is correct |
7 |
Execution timed out |
1004 ms |
133572 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 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 |
2 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 |
1092 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 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 |
2 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 |
5 ms |
1152 KB |
Output is correct |
14 |
Correct |
4 ms |
1152 KB |
Output is correct |
15 |
Correct |
3 ms |
1152 KB |
Output is correct |
16 |
Correct |
3 ms |
1152 KB |
Output is correct |
17 |
Correct |
4 ms |
1152 KB |
Output is correct |
18 |
Correct |
3 ms |
1092 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 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 |
2 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 |
59 ms |
13688 KB |
Output is correct |
12 |
Correct |
112 ms |
27000 KB |
Output is correct |
13 |
Correct |
185 ms |
66812 KB |
Output is correct |
14 |
Execution timed out |
1004 ms |
133572 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |