oj.uz

Submission #408804

# Submission time Handle Problem Language Result Execution time Memory
408804 2021-05-19T16:31:28 Z codebuster_10 Wall (IOI14_wall) C++17
100 / 100
 874 ms 59360 KB 
#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.0 / 8.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 348 KB Output is correct
4 Correct 8 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 157 ms 13908 KB Output is correct
3 Correct 244 ms 7924 KB Output is correct
4 Correct 594 ms 20132 KB Output is correct
5 Correct 365 ms 20676 KB Output is correct
6 Correct 335 ms 19092 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 348 KB Output is correct
4 Correct 8 ms 716 KB Output is correct
5 Correct 11 ms 684 KB Output is correct
6 Correct 6 ms 716 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 173 ms 13940 KB Output is correct
9 Correct 240 ms 7884 KB Output is correct
10 Correct 562 ms 20136 KB Output is correct
11 Correct 352 ms 20676 KB Output is correct
12 Correct 337 ms 19124 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 161 ms 13928 KB Output is correct
15 Correct 39 ms 1884 KB Output is correct
16 Correct 719 ms 20108 KB Output is correct
17 Correct 381 ms 19652 KB Output is correct
18 Correct 358 ms 19640 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 4 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 9 ms 716 KB Output is correct
6 Correct 6 ms 716 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 155 ms 13872 KB Output is correct
9 Correct 281 ms 8012 KB Output is correct
10 Correct 554 ms 20216 KB Output is correct
11 Correct 421 ms 20764 KB Output is correct
12 Correct 346 ms 19200 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 163 ms 13956 KB Output is correct
15 Correct 51 ms 1892 KB Output is correct
16 Correct 699 ms 20212 KB Output is correct
17 Correct 361 ms 19636 KB Output is correct
18 Correct 394 ms 19524 KB Output is correct
19 Correct 856 ms 59360 KB Output is correct
20 Correct 839 ms 59276 KB Output is correct
21 Correct 854 ms 59328 KB Output is correct
22 Correct 840 ms 59260 KB Output is correct
23 Correct 827 ms 59300 KB Output is correct
24 Correct 844 ms 59304 KB Output is correct
25 Correct 821 ms 59332 KB Output is correct
26 Correct 850 ms 59256 KB Output is correct
27 Correct 874 ms 59304 KB Output is correct
28 Correct 831 ms 59240 KB Output is correct
29 Correct 851 ms 59244 KB Output is correct
30 Correct 821 ms 59268 KB Output is correct