Submission #1109043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109043		Ludissey	Wall (IOI14_wall)	C++17	100 / 100	802 ms	230556 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#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;
    int lazy=-1;
    bool lazyOP=0;
    int lazy2=-1;
    bool lazy2OP=0;
    void update(){
      sum=left->sum+right->sum;
    }
};
 
struct segtree {
  int n;
  node* root=new node{nullptr,nullptr,0,-1,false,-1,false};

  void add(node* x, int v, bool t){
    if(x->lazy<0){
      x->lazyOP=t;
      x->lazy=v;
    }else if(x->lazy2<0) {
      if(x->lazyOP==t) {
        if(t==0) x->lazy=max(x->lazy,v);
        else x->lazy=min(x->lazy,v);
      }else{
        x->lazy2OP=t;
        x->lazy2=v;
      }
    }else if(x->lazy2OP==t){
      if(t==0) x->lazy2=max(x->lazy2,v);
      else x->lazy2=min(x->lazy2,v);
    }else{
      if(t==0) {
        if(x->lazy2<=v){
          x->lazy=x->lazy2;
          x->lazyOP=x->lazy2OP;
          x->lazy2=v;
          x->lazy2OP=t;
        }else{
          if(x->lazy2>x->lazy) x->lazy=max(x->lazy,v);
        }
      }
      else {
        if(x->lazy2>=v){
          x->lazy=x->lazy2;
          x->lazyOP=x->lazy2OP;
          x->lazy2=v;
          x->lazy2OP=t;
        }else{
          if(x->lazy2<x->lazy) x->lazy=min(x->lazy,v);
        }
      }
    }
  }

  void propagate(node* x){
    if(x->lazy>-1){
      if(x->left==nullptr){
        if(x->lazyOP==0) x->sum=max(x->sum,x->lazy);
        else x->sum=min(x->sum,x->lazy);
        if(x->lazy2>-1){
          if(x->lazy2OP==0) x->sum=max(x->sum,x->lazy2);
          else x->sum=min(x->sum,x->lazy2);
          x->lazy2=-1;
        }
        x->lazy=-1;
        return;
      }
      if(x->lazy2>-1){
        add(x->left,x->lazy,x->lazyOP);
        add(x->right,x->lazy,x->lazyOP);
        x->lazy=x->lazy2;
        x->lazyOP=x->lazy2OP;
        x->lazy2=-1;
      }
      add(x->left,x->lazy,x->lazyOP);
      add(x->right,x->lazy,x->lazyOP);
      x->lazy=-1;
    }
  }

  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){
      add(x,v,1);
      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){
      add(x,v,0);
      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,-1,false,-1,false};
    x->right=new node{nullptr,nullptr,0,-1,false,-1,false};
    build(x->left,l,mid);
    build(x->right,mid+1,r);
    x->update();
  }
  int query(node* x, int l, int r, int p){
    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: 29 / 29
• Subtask 4: 39 / 39