#include<bits/stdc++.h>
#define MAX_N 300005
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pil;
struct node{
LL s,e,y,idx;
}arr[MAX_N];
struct Tree{
LL maxx,ch_val,from;
}tree[4*MAX_N];
struct Range{
LL s,e;
}range[MAX_N];
LL n,m,k;
LL val[MAX_N],h[MAX_N],pa[MAX_N],V[MAX_N];
LL E,cnt,ans;
bool chk[MAX_N];
stack<LL> st;
vector<LL> net[MAX_N];
void update(LL x,LL l,LL r,LL ps,LL pe,LL v,LL F){
if(pe<l || ps>r) return;
if(l>r) return;
LL mid=(l+r)>>1;
if(ps<=l && r<=pe){
tree[x].ch_val+=v;
tree[x].maxx+=v;
if(ps==pe && F!=k+2) tree[x].from=F;
return;
}
update(2*x,l,mid,ps,pe,v,F);
update(2*x+1,mid+1,r,ps,pe,v,F);
tree[x].from=tree[2*x].from;
if(tree[2*x].maxx<tree[2*x+1].maxx) tree[x].from=tree[2*x+1].from;
tree[x].maxx=max(tree[2*x].maxx,tree[2*x+1].maxx)+tree[x].ch_val;
}
void dfs(LL x){
range[x].s=++cnt;
chk[x]=true;
V[x]=V[pa[x]]+val[x];
for(LL y:net[x]){
if(chk[y]) continue;
dfs(y);
}
range[x].e=cnt;
}
int main(){
LL i,x,y;
scanf("%lld",&n);
scanf("%*d %*d");
m=0;
for(i=2;i<n;i+=2){
m++;
scanf("%lld %lld",&arr[m].s,&arr[m].y);
scanf("%lld %*d",&arr[m].e);
arr[m].y++;
}
scanf("%*d %*d");
E=arr[m].e;
st.push(0);
k=0;
for(i=1;i<=m;i++){
while(!st.empty() && arr[st.top()].y>arr[i].y) st.pop();
if(arr[i].y==arr[st.top()].y){
arr[i].idx=arr[st.top()].idx;
val[arr[i].idx]+=(arr[i].e-arr[st.top()].e);
st.pop();
}else{
arr[i].idx=++k;
val[arr[i].idx]=(arr[i].e-arr[st.top()].e);
h[arr[i].idx]=arr[i].y;
pa[arr[i].idx]=arr[st.top()].idx;
}
st.push(i);
}
while(!st.empty()) st.pop();
arr[m+1].s=arr[m+1].e=E;
st.push(m+1);
for(i=m;i>=1;i--){
while(!st.empty() && arr[st.top()].y>=arr[i].y) st.pop();
if(h[pa[arr[i].idx]]<arr[st.top()].y) pa[arr[i].idx]=arr[st.top()].idx;
if(!chk[arr[i].idx])val[arr[i].idx]+=arr[st.top()].s-arr[i].e;
chk[arr[i].idx]=true;
st.push(i);
}
while(!st.empty()) st.pop();
for(i=0;i<=k;i++){
chk[i]=false;
val[i]*=(h[i]-h[pa[i]]);
}
for(i=1;i<=k;i++) net[pa[i]].pb(i);
cnt=0;
dfs(0);
for(i=0;i<=k;i++) update(1,1,cnt,range[i].s,range[i].s,V[i],i);
scanf("%lld",&m);
if(!m) return !printf("0\n");
while(m--){
x=tree[1].maxx;
y=tree[1].from;
ans+=x;
while(y && chk[y]){
chk[y]=false;
update(1,1,cnt,range[y].s,range[y].e,-val[y],k+2);
y=pa[y];
}
}
printf("%lld\n",ans-E);
return 0;
}
Compilation message
aqua3.cpp: In function 'int main()':
aqua3.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
aqua3.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%*d %*d");
~~~~~^~~~~~~~~~~
aqua3.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld",&arr[m].s,&arr[m].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua3.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %*d",&arr[m].e);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
aqua3.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%*d %*d");
~~~~~^~~~~~~~~~~
aqua3.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&m);
~~~~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
7544 KB |
Output is correct |
2 |
Correct |
4 ms |
7664 KB |
Output is correct |
3 |
Correct |
9 ms |
7664 KB |
Output is correct |
4 |
Correct |
9 ms |
7664 KB |
Output is correct |
5 |
Correct |
11 ms |
7720 KB |
Output is correct |
6 |
Correct |
10 ms |
7792 KB |
Output is correct |
7 |
Correct |
12 ms |
7820 KB |
Output is correct |
8 |
Correct |
11 ms |
7820 KB |
Output is correct |
9 |
Correct |
12 ms |
7940 KB |
Output is correct |
10 |
Correct |
11 ms |
7956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
8252 KB |
Output is correct |
2 |
Correct |
14 ms |
8308 KB |
Output is correct |
3 |
Correct |
13 ms |
8356 KB |
Output is correct |
4 |
Correct |
14 ms |
8424 KB |
Output is correct |
5 |
Correct |
14 ms |
8484 KB |
Output is correct |
6 |
Correct |
16 ms |
8800 KB |
Output is correct |
7 |
Correct |
14 ms |
8800 KB |
Output is correct |
8 |
Correct |
13 ms |
8800 KB |
Output is correct |
9 |
Correct |
15 ms |
8856 KB |
Output is correct |
10 |
Correct |
15 ms |
9044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
220 ms |
27564 KB |
Output is correct |
2 |
Correct |
180 ms |
27564 KB |
Output is correct |
3 |
Correct |
198 ms |
27564 KB |
Output is correct |
4 |
Correct |
162 ms |
32256 KB |
Output is correct |
5 |
Correct |
196 ms |
38056 KB |
Output is correct |
6 |
Correct |
246 ms |
59932 KB |
Output is correct |
7 |
Correct |
224 ms |
59932 KB |
Output is correct |
8 |
Correct |
171 ms |
59932 KB |
Output is correct |
9 |
Correct |
224 ms |
71124 KB |
Output is correct |
10 |
Correct |
229 ms |
77076 KB |
Output is correct |
11 |
Correct |
317 ms |
89228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
162 ms |
89228 KB |
Output is correct |
2 |
Correct |
224 ms |
89228 KB |
Output is correct |
3 |
Correct |
203 ms |
89228 KB |
Output is correct |
4 |
Correct |
232 ms |
89228 KB |
Output is correct |
5 |
Correct |
224 ms |
89228 KB |
Output is correct |
6 |
Correct |
315 ms |
106504 KB |
Output is correct |
7 |
Correct |
190 ms |
106504 KB |
Output is correct |
8 |
Correct |
177 ms |
106504 KB |
Output is correct |
9 |
Correct |
242 ms |
117664 KB |
Output is correct |
10 |
Correct |
242 ms |
123516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
281 ms |
123516 KB |
Output is correct |
2 |
Correct |
319 ms |
123516 KB |
Output is correct |
3 |
Correct |
241 ms |
123516 KB |
Output is correct |
4 |
Correct |
229 ms |
123516 KB |
Output is correct |
5 |
Correct |
224 ms |
125288 KB |
Output is correct |
6 |
Correct |
190 ms |
128624 KB |
Output is correct |
7 |
Runtime error |
265 ms |
132096 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
8 |
Halted |
0 ms |
0 KB |
- |