Submission #408804

#	Time	Username	Problem	Language	Result	Execution time	Memory
408804		codebuster_10	Wall (IOI14_wall)	C++17	100 / 100	874 ms	59360 KiB

wall

#include <bits/stdc++.h>
 
using namespace std ;
 
//#define int int64_t //be careful about this 
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)
 
#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound  
#define UB upper_bound
#define PQ priority_queue
 
#define sz(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem0(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))
 
template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}
 
void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  cin.exceptions(cin.failbit); 
	cout.precision(15);	cout << fixed;
  #ifdef ONLINE_JUDGE
  if(sz(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
  #define __f(...) 0
  #endif
}
 
 
/* 
  * Description segment tree for mass changes using lazy propagation
  * source: pashka edu course with very little own modifications 
  * verify commutivity and distributivity property for changes, assignement ans sum do not follow these property
  * set ID, NEUTRAL_ELEMENT, NO_OPERATION accordingly.
  * update on interval [l, r) and query val at range [l, r)
  * change x tells that at x this change is done but have to propogate to children
  * verification :- https://codeforces.com/edu/course/2/lesson/5/2/practice/status
*/
 
const int inf = 1e9;
 
struct operation {
	int a,b;
	operation(){
		a = 0, b = inf;
	}
}O;
template<class H> struct lazy_segment_tree { 
  const H NO_OPERATION = O;
  int size ;
  vector<H> change;
 
  void apply_lazy_on_change(H &A, H B){ 
    int a = A.a, b = A.b;
    assert(a <= b);
    int c = B.a, d = B.b;
    assert(c <= d);
    
    if(c < a){
    	a = a;
    }else if(c <= b){
    	a = c;
    }else{
    	a = b = c;
    }
    
    if(d < a){
    	a = b = d;
    }else if(d <= b){
    	b = d;
    }else{
    	b = b;
    }
    
    A.a = a, A.b = b; 
  }
    
  void propogate(int x, int lx, int rx){
    if(rx - lx == 1) return ;
    apply_lazy_on_change(change[2 * x + 1], change[x]);
    apply_lazy_on_change(change[2 * x + 2], change[x]);
    change[x] = NO_OPERATION;
  }
  
  void init(int n){ 
    size = 1;
    while(size < n) size *= 2;
		change.assign(2*size, NO_OPERATION); 
  }
  
	void update(int l, int r, int x, int lx, int rx, H value) { 
    propogate(x, lx, rx) ;
    if( lx >= r || l >= rx ){
      return;
    }
    if( lx >= l && rx <= r){
      apply_lazy_on_change(change[x], value);  
      return ;
    }
    int mid = (rx + lx)/2 ;
  	update(l, r, 2 * x + 1, lx, mid, value); 
		update(l, r, 2 * x + 2, mid, rx, value); 
		return ;
  }
  
  void update(int l, int r, H value) { 
    update(l, r, 0, 0, size, value) ; return ;
  }
  void propogate_all(){
  	propogate_all(0, 0, size);
  }
  void propogate_all(int x, int lx, int rx){
  	propogate(x, lx, rx);
  	if(rx - lx == 1) return;
  	int mid = (lx + rx)/2;
  	propogate_all(2 * x + 1, lx, mid);
  	propogate_all(2 * x + 2, mid, rx);
  }
};
 
void buildWall(int _n, int _k, int _op[], int _left[], int _right[], int _height[], int _finalHeight[]){
  setIO() ;
  int n = _n, q = _k; //rd(n,q);
  lazy_segment_tree<operation> st;
  st.init(n);
  f(i,0,q){
  	int t = _op[i], l = _left[i], r = _right[i], h = _height[i]; ++r;
  	if(t == 1){
  		operation c;
  		c.a = h, c.b = inf;
  		st.update(l,r,c);
  	}else{
  		operation c;
  		c.a = 0, c.b = h;
  		st.update(l,r,c);
  	}
  }
  st.propogate_all();
  f(i,0,n) _finalHeight[i] = st.change[i + st.size - 1].a;
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39