oj.uz

Submission #438419

# Submission time Handle Problem Language Result Execution time Memory
438419 2021-06-28T00:51:24 Z adamjinwei Wall (IOI14_wall) C++14
100 / 100
 978 ms 86088 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define inf 1000000007
#define mod 1000000007
#define lson (p<<1)
#define rson (p<<1|1)
#define rnd() rand_num()
#define bigrnd() dis(rand_num)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
//#define int long long
using namespace std;
unsigned sed=std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(sed);
uniform_int_distribution<long long> dis(0,inf);
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
template <typename T> void write(T x) {
	if (x<0) x=-x,putchar('-');
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int mx[8000005],mn[8000005],tag[8000005];
void pushup(int p)
{
	mx[p]=max(mx[lson],mx[rson]);
	mn[p]=min(mn[lson],mn[rson]);
}
void build(int p,int l,int r)
{
	if(l==r)
	{
		mx[p]=mn[p]=0;
		tag[p]=-1;
		return;
	}
	int mid=l+r>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	pushup(p);
}
void pushdown(int p)
{
	if(tag[p]!=-1)
	{
		mx[lson]=mn[lson]=tag[lson]=mx[rson]=mn[rson]=tag[rson]=tag[p];
		tag[p]=-1;
	}
}
void add(int p,int l,int r,int x,int y,int k)
{
	if(mn[p]>=k) return;
	if(x<=l&&r<=y)
	{
		if(mx[p]<=k)
		{
			mx[p]=mn[p]=tag[p]=k;
			return;
		}
	}
	pushdown(p);
	int mid=l+r>>1;
	if(x<=mid) add(lson,l,mid,x,y,k);
	if(mid+1<=y) add(rson,mid+1,r,x,y,k);
	pushup(p);
}
void remove(int p,int l,int r,int x,int y,int k)
{
	if(mx[p]<=k) return;
	if(x<=l&&r<=y)
	{
		if(mn[p]>=k)
		{
			mx[p]=mn[p]=tag[p]=k;
			return;
		}
	}
	pushdown(p);
	int mid=l+r>>1;
	if(x<=mid) remove(lson,l,mid,x,y,k);
	if(mid+1<=y) remove(rson,mid+1,r,x,y,k);
	pushup(p);
}
int query(int p,int l,int r,int x)
{
	if(l==r)
		return mx[p];
	pushdown(p);
	int mid=l+r>>1;
	if(x<=mid) return query(lson,l,mid,x);
	else return query(rson,mid+1,r,x);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
	build(1,1,n);
	for(int i=0;i<k;++i)
	{
		if(op[i]==1)
			add(1,1,n,left[i]+1,right[i]+1,height[i]);
		else
			remove(1,1,n,left[i]+1,right[i]+1,height[i]);
	}
	for(int i=0;i<n;++i)
		finalHeight[i]=query(1,1,n,i+1);
}

Compilation message

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:45:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |  int mid=l+r>>1;
      |          ~^~
wall.cpp: In function 'void add(int, int, int, int, int, int)':
wall.cpp:70:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |  int mid=l+r>>1;
      |          ~^~
wall.cpp: In function 'void remove(int, int, int, int, int, int)':
wall.cpp:87:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |  int mid=l+r>>1;
      |          ~^~
wall.cpp: In function 'int query(int, int, int, int)':
wall.cpp:97:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |  int mid=l+r>>1;
      |          ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 6 ms 892 KB Output is correct
5 Correct 6 ms 844 KB Output is correct
6 Correct 6 ms 844 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 158 ms 13896 KB Output is correct
3 Correct 81 ms 8196 KB Output is correct
4 Correct 227 ms 21356 KB Output is correct
5 Correct 222 ms 22480 KB Output is correct
6 Correct 229 ms 20960 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 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 6 ms 972 KB Output is correct
5 Correct 6 ms 888 KB Output is correct
6 Correct 9 ms 892 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 156 ms 13868 KB Output is correct
9 Correct 80 ms 8168 KB Output is correct
10 Correct 199 ms 21360 KB Output is correct
11 Correct 280 ms 22468 KB Output is correct
12 Correct 225 ms 20892 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 160 ms 14096 KB Output is correct
15 Correct 28 ms 2216 KB Output is correct
16 Correct 481 ms 21700 KB Output is correct
17 Correct 313 ms 21060 KB Output is correct
18 Correct 304 ms 21100 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 2 ms 460 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 6 ms 972 KB Output is correct
5 Correct 6 ms 844 KB Output is correct
6 Correct 6 ms 972 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 158 ms 13904 KB Output is correct
9 Correct 80 ms 8372 KB Output is correct
10 Correct 196 ms 21336 KB Output is correct
11 Correct 205 ms 22468 KB Output is correct
12 Correct 223 ms 20804 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 161 ms 13900 KB Output is correct
15 Correct 29 ms 2180 KB Output is correct
16 Correct 477 ms 21648 KB Output is correct
17 Correct 305 ms 21064 KB Output is correct
18 Correct 300 ms 21108 KB Output is correct
19 Correct 928 ms 85956 KB Output is correct
20 Correct 935 ms 83576 KB Output is correct
21 Correct 927 ms 86024 KB Output is correct
22 Correct 935 ms 83528 KB Output is correct
23 Correct 939 ms 83428 KB Output is correct
24 Correct 937 ms 83400 KB Output is correct
25 Correct 933 ms 83368 KB Output is correct
26 Correct 925 ms 86088 KB Output is correct
27 Correct 945 ms 85984 KB Output is correct
28 Correct 926 ms 83384 KB Output is correct
29 Correct 978 ms 83380 KB Output is correct
30 Correct 922 ms 83652 KB Output is correct