oj.uz

Submission #58821

# Submission time Handle Problem Language Result Execution time Memory
58821 2018-07-19T14:47:52 Z fefe 수족관 3 (KOI13_aqua3) C++17
84 / 100
 319 ms 132096 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;
}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);
  ~~~~~^~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory 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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory 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

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory 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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory 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

Subtask #5
0 / 16.0

# Verdict Execution time Memory 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 -