Submission #480192

#	Time	Username	Problem	Language	Result	Execution time	Memory
480192		dsyz	Wall (IOI14_wall)	C++17	0 / 100	223 ms	11304 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = long long;
#define MAXN (1000005)

struct node{
  int s,e,m,v,lazyaddatleast,lazyaddatmost;
  node *l,*r;
  node(int _s,int _e){
    s = _s;
    e = _e;
    m = (s + e) / 2;
    v = 0;
    lazyaddatleast = 0;
    lazyaddatmost = 0;
    if(s != e){
      l = new node(s,m);
      r = new node(m + 1,e);
    }
  }
  int value(){
    if(s == e){
		v = max(v,lazyaddatleast);
		v = min(v,lazyaddatmost);
		return v;
    }                                                             
    v = max(v,lazyaddatleast);
    v = min(v,lazyaddatmost);
    r->lazyaddatleast = max(lazyaddatleast,r->lazyaddatleast);
    r->lazyaddatmost = min(lazyaddatmost,r->lazyaddatmost);
    l->lazyaddatleast = max(lazyaddatleast,l->lazyaddatleast);
    l->lazyaddatmost = min(lazyaddatmost,l->lazyaddatmost);
    if(l->lazyaddatmost < l->lazyaddatleast){ //keep lazyaddatmost always larger than lazyaddatleast
		l->lazyaddatmost = 1000000; //INF , but must also fufil lazyadd
	}
	if(r->lazyaddatmost < r->lazyaddatleast){ //keep lazyaddatmost always larger than lazyaddatleast
		r->lazyaddatmost = 1000000; //INF
	}	
    return v;
  }
  void atleast(int x,int y,int val){
    if(s == x && e == y){
		lazyaddatleast = val;
		if(lazyaddatmost < lazyaddatleast){ //keep lazyaddmost always larger than lazyaddleast
			lazyaddatmost = 1000000; //INF
		}		
	}else{
		if(x > m) r -> atleast(x,y,val);
		else if(y <= m) l -> atleast(x,y,val);
		else l -> atleast(x,m,val), r -> atleast(m + 1,y,val);
		v = l->value() + r->value();
    }
  }
  void atmost(int x,int y,int val){
    if(s == x && e == y){
		lazyaddatmost = val;
		if(lazyaddatmost < lazyaddatleast){ //keep lazyaddmost always larger than lazyaddleast
			lazyaddatleast = 0;
		}	
	}else{
      if(x > m) r -> atmost(x,y,val);
      else if(y <= m) l -> atmost(x,y,val);
      else l -> atmost(x,m,val), r -> atmost(m + 1,y,val);
      v = l->value() + r->value();
    }
  }
  int query(int x,int y){
      value();
      if(s == x && e == y) return value();
      if(x > m) return r -> query(x,y);
      if(y <= m) return l -> query(x,y);
      return l -> query(x,m) + r -> query(m + 1,y);
  }
} *root;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	root = new node(0,n + 5);
	for(ll i = 0;i < k;i++){
		if(op[i] == 1){
			root->atleast(left[i],right[i],height[i]);
		}else if(op[i] == 2){
			root->atmost(left[i],right[i],height[i]);
		}
	}
	for(ll i = 0;i < n;i++){
		ll a = root->query(i,i);
		finalHeight[i] = a;
	}
	return;
}

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