oj.uz

Submission #375147

# Submission time Handle Problem Language Result Execution time Memory
375147 2021-03-09T03:42:04 Z PixelCat Wall (IOI14_wall) C++14
100 / 100
 742 ms 66540 KB 
/*                                                       
  /^--^\                                                 
  \____/                                                 
 /      \ _____  _ __  __ ____  _     ____   ____  _____ 
|        || ()_)| |\ \/ /| ===|| |__ / (__` / () \|_   _|
 \__  __/ |_|   |_|/_/\_\|____||____|\____)/__/\__\ |_|  
|^|^\ \^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|
| | |\ \| | | | | | | | | | | | | | | | | | | | | | | | |
#####/ /#################################################
| | |\/ | | | | | | | | | | | | | | | | | | | | | | | | |
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|*/
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#include <wall.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<ll,ll>;
//#define int ll //__int128
#define double long double

#define For(i,a,b)  for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define L(id) (id*2+1)
#define R(id) (id*2+2)
#define LO(x) (x&(-x))

#define eb emplace_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (ll)(1000000007)
#define INF (ll)(1e17)
#define EPS (1e-9)

#ifdef LOCALMEOW
#define debug(...) do{\
	cerr << __LINE__ <<\
	" : ("#__VA_ARGS__ << ") = ";\
	_OUT(__VA_ARGS__);\
}while(0)
template<typename T> void _OUT(T x) { cerr << x << "\n"; }
template<typename T,typename...I>
void _OUT(T x,I ...tail) { cerr << x << ", "; _OUT(tail...); }
#else
#define debug(...)
#endif
inline void NYA(){ ios::sync_with_stdio(false); cin.tie(0); }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p){
	int ans=1,now=b;
	while(p){
		if(p&1) ans=ans*now%MOD;
		p/=2; now=now*now%MOD;
	}
	return ans;
}
void minify(int &a,const int &b) { if(b<a) a=b; }
void maxify(int &a,const int &b) { if(b>a) a=b; }

struct SegTree{
	int lo[8000080];
	int hi[8000080];
	#define tag(a,b,c) a=min(max(a,b),c)
	void push(int id){
		if(lo[id]==-INF && hi[id]==INF) return;
		tag(lo[L(id)],lo[id],hi[id]);
		tag(hi[L(id)],lo[id],hi[id]);
		tag(lo[R(id)],lo[id],hi[id]);
		tag(hi[R(id)],lo[id],hi[id]);
		lo[id]=-INF; hi[id]=INF;
	}
	void build(int id,int l,int r){
		if(l==r){
			lo[id]=hi[id]=0;
			return;
		}
		lo[id]=-INF;
		hi[id]=INF;
		int m=(l+r)/2;
		build(L(id),l,m);
		build(R(id),m+1,r);
	}
	void updhi(int id,int l,int r,int L,int R,int x){
		if(l>R || r<L) return;
		if(l>=L && r<=R){
			minify(hi[id],x);
			minify(lo[id],x);
			return;
		}
		int m=(l+r)/2;
		push(id);
		updhi(L(id),l,m,L,R,x);
		updhi(R(id),m+1,r,L,R,x);
	}
	void updlo(int id,int l,int r,int L,int R,int x){
		if(l>R || r<L) return;
		if(l>=L && r<=R){
			maxify(hi[id],x);
			maxify(lo[id],x);
			return;
		}
		int m=(l+r)/2;
		push(id);
		updlo(L(id),l,m,L,R,x);
		updlo(R(id),m+1,r,L,R,x);
	}
	void ask(int id,int l,int r,int ans[]){
		if(l==r){
			ans[l]=lo[id];
			return;
		}
		int m=(l+r)/2;
		push(id);
		ask(L(id),l,m,ans);
		ask(R(id),m+1,r,ans);
	}
}seg;

void buildWall(int n,int q,int op[],int l[],int r[],int h[], int final[]){
	seg.build(0,0,n-1);
	For(i,0,q-1){
		if(op[i]==1) seg.updlo(0,0,n-1,l[i],r[i],h[i]);
		else         seg.updhi(0,0,n-1,l[i],r[i],h[i]);
	}
	seg.ask(0,0,n-1,final);
}

#ifdef LOCALMEOW
int32_t main(){
	//shinon >//////<
	int n=10,q=6;
	int op[6]={1,2,2,1,1,2};
	int l[6]={1,4,3,0,2,6};
	int r[6]={8,9,6,5,2,7};
	int h[6]={4,1,5,3,5,0};
	int fin[10];
	buildWall(n,q,op,l,r,h,fin);
	For(i,0,9) cout<<fin[i]<<"\n"; 
}
#endif

Compilation message

wall.cpp: In member function 'void SegTree::push(int)':
wall.cpp:77:10: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '-100000000000000000' to '-1569325056' [-Woverflow]
   77 |   lo[id]=-INF; hi[id]=INF;
      |          ^
wall.cpp:36:13: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '100000000000000000' to '1569325056' [-Woverflow]
   36 | #define INF (ll)(1e17)
      |             ^~~~~~~~~~
wall.cpp:77:23: note: in expansion of macro 'INF'
   77 |   lo[id]=-INF; hi[id]=INF;
      |                       ^~~
wall.cpp: In member function 'void SegTree::build(int, int, int)':
wall.cpp:84:10: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '-100000000000000000' to '-1569325056' [-Woverflow]
   84 |   lo[id]=-INF;
      |          ^
wall.cpp:36:13: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '100000000000000000' to '1569325056' [-Woverflow]
   36 | #define INF (ll)(1e17)
      |             ^~~~~~~~~~
wall.cpp:85:10: note: in expansion of macro 'INF'
   85 |   hi[id]=INF;
      |          ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 6 ms 876 KB Output is correct
5 Correct 5 ms 876 KB Output is correct
6 Correct 5 ms 876 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 152 ms 13932 KB Output is correct
3 Correct 187 ms 8044 KB Output is correct
4 Correct 475 ms 18028 KB Output is correct
5 Correct 305 ms 18540 KB Output is correct
6 Correct 289 ms 18796 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 6 ms 840 KB Output is correct
5 Correct 5 ms 876 KB Output is correct
6 Correct 5 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 158 ms 13932 KB Output is correct
9 Correct 181 ms 8044 KB Output is correct
10 Correct 483 ms 18028 KB Output is correct
11 Correct 303 ms 18560 KB Output is correct
12 Correct 292 ms 18796 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 160 ms 14060 KB Output is correct
15 Correct 34 ms 2028 KB Output is correct
16 Correct 521 ms 18284 KB Output is correct
17 Correct 307 ms 18368 KB Output is correct
18 Correct 289 ms 18416 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 6 ms 876 KB Output is correct
5 Correct 5 ms 876 KB Output is correct
6 Correct 5 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 152 ms 13932 KB Output is correct
9 Correct 181 ms 8172 KB Output is correct
10 Correct 468 ms 18096 KB Output is correct
11 Correct 299 ms 18412 KB Output is correct
12 Correct 290 ms 18796 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 159 ms 13996 KB Output is correct
15 Correct 30 ms 2028 KB Output is correct
16 Correct 513 ms 18284 KB Output is correct
17 Correct 299 ms 18412 KB Output is correct
18 Correct 296 ms 18412 KB Output is correct
19 Correct 734 ms 66540 KB Output is correct
20 Correct 732 ms 63948 KB Output is correct
21 Correct 734 ms 66444 KB Output is correct
22 Correct 729 ms 64020 KB Output is correct
23 Correct 725 ms 63880 KB Output is correct
24 Correct 736 ms 63852 KB Output is correct
25 Correct 732 ms 63900 KB Output is correct
26 Correct 740 ms 66284 KB Output is correct
27 Correct 742 ms 66296 KB Output is correct
28 Correct 732 ms 63852 KB Output is correct
29 Correct 721 ms 63852 KB Output is correct
30 Correct 725 ms 63852 KB Output is correct