제출 #1109000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1109000		Ludissey	Wall (IOI14_wall)	C++17	32 / 100	3063 ms	40576 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

int n,q; 
vector<pair<pair<int,int>,int>> qrs;



struct node {
    node* left;
    node* right;
    int sum=0;
    bool markedMN=false;
    bool markedMX=false;
    int lazy=0;
    void update(){
      sum=left->sum+right->sum;
    }
};
 
struct segtree {
  int n;
  node* root=new node{nullptr,nullptr,0,false,false,0};
  void propagate(node* x){
    if(x->markedMN){
      if(x->left==NULL){
        x->sum=min(x->sum,x->lazy);
        x->markedMN=false;
        return;
      }
      if(x->left->markedMN){
        x->left->lazy=min(x->left->lazy, x->lazy);
      }else {
        if(x->left->markedMX) propagate(x->left);
        x->left->lazy=x->lazy;
        x->left->markedMN=true;
      }
      if(x->right->markedMN){
        x->right->lazy=min(x->right->lazy, x->lazy);
      }else {
        if(x->right->markedMX) propagate(x->right);
        x->right->lazy=x->lazy;
        x->right->markedMN=true;
      }
      x->markedMN=false;
      x->lazy=0;
    }else if(x->markedMX){
      if(x->left==NULL){
        x->sum=max(x->sum,x->lazy);
        x->markedMX=false;
        return;
      }
      if(x->left->markedMX){
        x->left->lazy=max(x->left->lazy, x->lazy);
      }else {
        if(x->left->markedMN) propagate(x->left);
        x->left->lazy=x->lazy;
        x->left->markedMX=true;
      }
      if(x->right->markedMX){
        x->right->lazy=max(x->right->lazy, x->lazy);
      }else {
        if(x->right->markedMN) propagate(x->right);
        x->right->lazy=x->lazy;
        x->right->markedMX=true;
      }
      x->markedMX=false;
      x->lazy=0;
    }
  }

  void updateMN(node* x, int l, int r, int qL, int qR, int v){
    if(l>qR||r<qL) return;
    propagate(x);
    if(l>=qL&&r<=qR){
      x->lazy=v;
      x->markedMN=true;
      return;
    }
    int mid=(l+r)/2;
    updateMN(x->left,l,mid,qL,qR,v);
    updateMN(x->right,mid+1,r,qL,qR,v);
    x->update();
  }

  void updateMX(node* x, int l, int r, int qL, int qR, int v){
    if(l>qR||r<qL) return;
    propagate(x);
    if(l>=qL&&r<=qR){
      x->lazy=v;
      x->markedMX=true;
      return;
    }
    int mid=(l+r)/2;
    updateMX(x->left,l,mid,qL,qR,v);
    updateMX(x->right,mid+1,r,qL,qR,v);
    x->update();
  }

  void build(node* x, int l, int r){
      if(l==r){
          x->sum=0;
          return;
      }
      int mid=(l+r)/2;
      x->left=new node{nullptr,nullptr,0,false,false,0};
      x->right=new node{nullptr,nullptr,0,false,false,0};
      build(x->left,l,mid);
      build(x->right,mid+1,r);
      x->update();
  }
  int query(node* x, int l, int r, int p){
      if(r<p||l>p) return -1e9;
      propagate(x);
      if(l==p&&r==p) return x->sum;
      int mid=(l+r)/2;
      if(mid>=p) return query(x->left,l,mid,p); 
      else return query(x->right,mid+1,r,p);
  }
  void updateMN(int l, int r, int v){
    updateMN(root,0,n-1,l,r,v);
  }
  void updateMX(int l, int r, int v){
    updateMX(root,0,n-1,l,r,v);
  }
  int query(int p){
    return query(root,0,n-1,p);
  }
  segtree(int x){
    n=x;
    build(root,0,n-1);
  }
};

void buildWall(signed _n, signed _k, signed _op[], signed _left[], signed _right[], signed _height[], signed finalHeight[]){
  n=_n; q=_k;
  qrs.resize(q);
  segtree seg(n);

  for (int i = 0; i < q; i++)
  {
    int l=_left[i]; int r=_right[i];
    if(_op[i]==1) seg.updateMX(l,r,_height[i]);
    else seg.updateMN(l,r,_height[i]);
  }
  for (int i = 0; i < n; i++) finalHeight[i]=seg.query(i);
  return;
}

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