oj.uz

Submission #870846

# Submission time Handle Problem Language Result Execution time Memory
870846 2023-11-09T09:48:09 Z Hyojin Wall (IOI14_wall) C++17
100 / 100
 1213 ms 104604 KB 
#include <bits/stdc++.h>
using namespace std;
#define bit(n,i) ((n>>i)&1) 
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define ep emplace_back
#define pii pair<int,int>
#define piii pair<int,pii> 
#define fi first
#define se second
#define ll long long
#define debug(x) cerr << #x << ' ' << x << '\n'
#define dbg(x) cerr<<#x<<' '<<x<<' '
const int base=31;								
const int MOD=1e9+7;	
const int N=1e6+5;
const int INF=1e9;
const int mx=2e6;
struct segtree{
	int max1,max2,min1,min2;
} st[mx*4+5];
int n,m,k;
array<int,4>queries[N];
void pushMin(int id,int val)
{
	if (st[id].min1>=val)
	{
		st[id]={val,-INF,val,INF};
	}
	else if (val<st[id].max1)
	{
		if (st[id].min2==st[id].max1) st[id].min2=val;
		st[id].max1=val;
	}
}
void pushMax(int id,int val)
{
	if (st[id].max1<=val)
	{
		st[id]={val,-INF,val,INF};
	}
	else if (st[id].min1<val)
	{
		if (st[id].max2==st[id].min1) st[id].max2=val;
		st[id].min1=val;
	}
}
void up(int id)
{
	st[id].max1=max(st[id<<1].max1,st[id<<1|1].max1);
	st[id].max2=max(st[id<<1].max2,st[id<<1|1].max2);
	st[id].min1=min(st[id<<1].min1,st[id<<1|1].min1);
	st[id].min2=min(st[id<<1].min2,st[id<<1|1].min2);
	if (st[id<<1].max1!=st[id].max1) st[id].max2=max(st[id].max2,st[id<<1].max1);
	if (st[id<<1|1].max1!=st[id].max1) st[id].max2=max(st[id].max2,st[id<<1|1].max1);
	if (st[id<<1].min1!=st[id].min1) st[id].min2=min(st[id].min2,st[id<<1].min1);
	if (st[id<<1|1].min1!=st[id].min1) st[id].min2=min(st[id].min2,st[id<<1|1].min1);
}
void down(int id)
{
	pushMin(id<<1,st[id].max1);
	pushMin(id<<1|1,st[id].max1);
	pushMax(id<<1,st[id].min1);
	pushMax(id<<1|1,st[id].min1);
}
void updateMax(int id,int l,int r,int u,int v,int x)
{
	if (v<l||r<u||x<=st[id].min1) return;
	if (u<=l&&r<=v&&x<st[id].min2)
	{
		pushMax(id,x);
		return;
	}
	int mid=l+r>>1;
	down(id);
	updateMax(id<<1,l,mid,u,v,x);
	updateMax(id<<1|1,mid+1,r,u,v,x);
	up(id);
}
void updateMin(int id,int l,int r,int u,int v,int x)
{
	if (v<l||r<u||x>=st[id].max1) return;
	if (u<=l&&r<=v&&st[id].max2<x)
	{
		pushMin(id,x);
		return;
	}
	int mid=l+r>>1;
	down(id);
	updateMin(id<<1,l,mid,u,v,x);
	updateMin(id<<1|1,mid+1,r,u,v,x);
	up(id);
}
int get(int id,int l,int r,int x)
{
	if (l==r) return st[id].max1;
	int mid=l+r>>1;
	down(id);
	if (x<=mid) return get(id<<1,l,mid,x);
	return get(id<<1|1,mid+1,r,x);
}
void build(int id,int l,int r)
{
	if (l==r)
	{
		st[id]={0,-INF,0,INF};
		return;
	}
	int mid=l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	up(id);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
	build(1,0,n-1);
	for (int i=0;i<k;i++)
	{
		if (op[i]==1)
		{
			updateMax(1,0,n-1,left[i],right[i],height[i]);
		} else updateMin(1,0,n-1,left[i],right[i],height[i]);
	}
	for (int i=0;i<n;i++)
	{
		finalHeight[i]=get(1,0,n-1,i);
	}
}
/* stuff you should look for						
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

wall.cpp: In function 'void updateMax(int, int, int, int, int, int)':
wall.cpp:74:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |  int mid=l+r>>1;
      |          ~^~
wall.cpp: In function 'void updateMin(int, int, int, int, int, int)':
wall.cpp:88:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |  int mid=l+r>>1;
      |          ~^~
wall.cpp: In function 'int get(int, int, int, int)':
wall.cpp:97:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |  int mid=l+r>>1;
      |          ~^~
wall.cpp: In function 'void build(int, int, int)':
wall.cpp:109:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |  int mid=l+r>>1;
      |          ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 8 ms 2652 KB Output is correct
5 Correct 6 ms 2692 KB Output is correct
6 Correct 6 ms 2652 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 97 ms 16064 KB Output is correct
3 Correct 59 ms 11636 KB Output is correct
4 Correct 179 ms 24540 KB Output is correct
5 Correct 163 ms 25596 KB Output is correct
6 Correct 204 ms 24016 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2392 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 8 ms 2700 KB Output is correct
5 Correct 7 ms 2652 KB Output is correct
6 Correct 6 ms 2652 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 100 ms 16116 KB Output is correct
9 Correct 63 ms 11604 KB Output is correct
10 Correct 157 ms 24620 KB Output is correct
11 Correct 163 ms 25696 KB Output is correct
12 Correct 201 ms 23892 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 103 ms 16128 KB Output is correct
15 Correct 37 ms 5712 KB Output is correct
16 Correct 567 ms 24828 KB Output is correct
17 Correct 333 ms 24084 KB Output is correct
18 Correct 334 ms 24244 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 7 ms 2652 KB Output is correct
5 Correct 7 ms 2648 KB Output is correct
6 Correct 6 ms 2696 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 99 ms 15952 KB Output is correct
9 Correct 61 ms 11644 KB Output is correct
10 Correct 151 ms 24412 KB Output is correct
11 Correct 161 ms 25480 KB Output is correct
12 Correct 212 ms 24152 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 102 ms 16100 KB Output is correct
15 Correct 41 ms 5572 KB Output is correct
16 Correct 585 ms 24824 KB Output is correct
17 Correct 331 ms 24144 KB Output is correct
18 Correct 329 ms 24300 KB Output is correct
19 Correct 1167 ms 104552 KB Output is correct
20 Correct 1146 ms 101832 KB Output is correct
21 Correct 1180 ms 104364 KB Output is correct
22 Correct 1181 ms 101888 KB Output is correct
23 Correct 1146 ms 102196 KB Output is correct
24 Correct 1133 ms 102060 KB Output is correct
25 Correct 1161 ms 101976 KB Output is correct
26 Correct 1176 ms 104604 KB Output is correct
27 Correct 1168 ms 104520 KB Output is correct
28 Correct 1167 ms 101896 KB Output is correct
29 Correct 1156 ms 101968 KB Output is correct
30 Correct 1213 ms 101956 KB Output is correct