oj.uz

Submission #399606

# Submission time Handle Problem Language Result Execution time Memory
399606 2021-05-06T08:55:44 Z Jasiekstrz Wall (IOI14_wall) C++17
100 / 100
 768 ms 69672 KB 
#include<bits/stdc++.h>
#include "wall.h"
#define fi first
#define se second
using namespace std;
const int N=2e6,K=5e5,MN=0,MX=1e5;
const int P=21e5;
int pot;
pair<int,int> tree[2*P+10];
void merge(pair<int,int> &x,pair<int,int> y)
{
	if(y.se<x.fi)
		x={y.se,y.se};
	else if(x.se<y.fi)
		x={y.fi,y.fi};
	else
	{
		x.fi=max(x.fi,y.fi);
		x.se=min(x.se,y.se);
	}
	return;
}
void push_down(int i)
{
	merge(tree[2*i],tree[i]);
	merge(tree[2*i+1],tree[i]);
	tree[i]={MN,MX};
	return;
}
void add_t(int i,int l,int r,int ls,int rs,pair<int,int> c)
{
	if(r<ls || rs<l)
		return;
	else if(ls<=l && r<=rs)
	{
		merge(tree[i],c);
		return;
	}
	push_down(i);
	int mid=(l+r)/2;
	add_t(2*i,l,mid,ls,rs,c);
	add_t(2*i+1,mid+1,r,ls,rs,c);
	return;
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
	for(pot=1;pot<n;pot*=2);
	for(int i=1;i<=2*pot;i++)
		tree[i]={MN,MX};
	for(int i=0;i<k;i++)
	{
		if(op[i]==1) // adding phase
			add_t(1,1,pot,left[i]+1,right[i]+1,{height[i],MX});
		else // removing phase
			add_t(1,1,pot,left[i]+1,right[i]+1,{MN,height[i]});
	}
	for(int i=1;i<pot;i++)
		push_down(i);
	for(int i=0;i<n;i++)
		finalHeight[i]=tree[i+pot].fi;
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 716 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 156 ms 13880 KB Output is correct
3 Correct 178 ms 7876 KB Output is correct
4 Correct 473 ms 20364 KB Output is correct
5 Correct 319 ms 21388 KB Output is correct
6 Correct 343 ms 19816 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 368 KB Output is correct
4 Correct 9 ms 828 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 7 ms 716 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 161 ms 13972 KB Output is correct
9 Correct 177 ms 7916 KB Output is correct
10 Correct 463 ms 20328 KB Output is correct
11 Correct 319 ms 21532 KB Output is correct
12 Correct 314 ms 19840 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 161 ms 14144 KB Output is correct
15 Correct 35 ms 1992 KB Output is correct
16 Correct 567 ms 20568 KB Output is correct
17 Correct 325 ms 20048 KB Output is correct
18 Correct 323 ms 20076 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 5 ms 820 KB Output is correct
6 Correct 6 ms 716 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 157 ms 13904 KB Output is correct
9 Correct 173 ms 7912 KB Output is correct
10 Correct 461 ms 20432 KB Output is correct
11 Correct 327 ms 21404 KB Output is correct
12 Correct 312 ms 19944 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 159 ms 13892 KB Output is correct
15 Correct 34 ms 2008 KB Output is correct
16 Correct 576 ms 20656 KB Output is correct
17 Correct 321 ms 20004 KB Output is correct
18 Correct 322 ms 20028 KB Output is correct
19 Correct 759 ms 69492 KB Output is correct
20 Correct 746 ms 67132 KB Output is correct
21 Correct 768 ms 69672 KB Output is correct
22 Correct 753 ms 67036 KB Output is correct
23 Correct 746 ms 67136 KB Output is correct
24 Correct 754 ms 66964 KB Output is correct
25 Correct 750 ms 67012 KB Output is correct
26 Correct 755 ms 69476 KB Output is correct
27 Correct 760 ms 69624 KB Output is correct
28 Correct 746 ms 66972 KB Output is correct
29 Correct 735 ms 66972 KB Output is correct
30 Correct 744 ms 66992 KB Output is correct