| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58810 |
2018-07-19T14:19:55 Z |
fefe |
수족관 3 (KOI13_aqua3) |
C++17 |
|
272 ms |
42928 KB |
#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,pa;
}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<int> st;
vector<int> 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[arr[i].pa]<arr[st.top()].y) pa[arr[i].idx]=arr[st.top()].idx;
val[arr[i].idx]+=arr[st.top()].s-arr[i].e;
st.push(i);
}
while(!st.empty()) st.pop();
for(i=0;i<=k;i++){
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);
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:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&m);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
7544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
8036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
184 ms |
32456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
200 ms |
37804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
272 ms |
42928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
