Submission #180365

#	Time	Username	Problem	Language	Result	Execution time	Memory
180365		FieryPhoenix	Wall (IOI14_wall)	C++11	100 / 100	2996 ms	125436 KiB

wall

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

struct LazySegmentTree{
  int siz;
  vector<ll>tree,lazyAdd,lazySub;
  LazySegmentTree(int temp){
    siz=temp;
    while ((siz&(siz-1))!=0) siz++;
    for (int i=0;i<siz*2;i++){
      tree.push_back(0);
      lazyAdd.push_back(-INF);
      lazySub.push_back(INF);
    }
  }
  void calc(int node){
    tree[node]=max(tree[node],lazyAdd[node]);
    tree[node]=min(tree[node],lazySub[node]);
  }
  void propagate(int node, int L, int R){
    calc(node);
    if (L!=R){
      calc(node*2);
      calc(node*2+1);
      applySub(node*2,lazySub[node]);
      applyAdd(node*2,lazyAdd[node]);
      applySub(node*2+1,lazySub[node]);
      applyAdd(node*2+1,lazyAdd[node]);
      calc(node*2);
      calc(node*2+1);
    }
    lazyAdd[node]=-INF;
    lazySub[node]=INF;
  }
  void applyAdd(int node, ll x){
    if (x>lazyAdd[node]){
      lazyAdd[node]=x;
      lazySub[node]=max(lazySub[node],x);
    }
  }
   void applySub(int node, ll x){
    if (x<lazySub[node]){
      lazySub[node]=x;
      lazyAdd[node]=min(lazyAdd[node],x);
    }
  }
  void update(int node, int L, int R, int i, int j, ll x, int type){
    propagate(node,L,R);
    if (L>R || L>j || R<i)
      return;
    if (L>=i && R<=j){
      if (type==1)
	applyAdd(node,x);
      else
	applySub(node,x);
      propagate(node,L,R);
      return;
    }
    update(node*2,L,(L+R)/2,i,j,x,type);
    update(node*2+1,(L+R)/2+1,R,i,j,x,type);
    //tree[node]=tree[node*2]+tree[node*2+1];
  }
  ll query(int node, int L, int R, int i,int j){
    if (L>R || L>j || R<i)
      return 0;
    propagate(node,L,R);
    //cout<<"QPOP "<<node<<endl;
    if (L>=i && R<=j){
      //cout<<"FOUND "<<node<<endl;
      return tree[node];
    }
    ll q1=query(node*2,L,(L+R)/2,i,j);
    ll q2=query(node*2+1,(L+R)/2+1,R,i,j);
    return q1+q2;
  }
  ll query(int i, int j){ return query(1,0,siz-1,i,j); }
  void update(int i, int j, ll val, int type){ update(1,0,siz-1,i,j,val,type); }
};

void buildWall(int N, int K, int op[], int l[], int r[], int h[], int finalh[]){
  LazySegmentTree lst=LazySegmentTree(N);
  for (int i=0;i<K;i++){
    lst.update(l[i],r[i],h[i],op[i]);
    /*
    bool debug=false;
    if (debug){
      cout<<"BEFORE: "<<endl;
      for (int j=1;j<lst.siz*2;j++)
	cout<<j<<": "<<lst.lazyAdd[j]<<' '<<lst.lazySub[j]<<endl;
    }
    for (int j=0;j<N;j++)
      cout<<lst.query(j,j)<<' ';
    cout<<endl;
    if (debug){
      cout<<"AFTER: "<<endl;
      for (int j=1;j<lst.siz*2;j++)
	cout<<j<<": "<<lst.lazyAdd[j]<<' '<<lst.lazySub[j]<<endl;
    }
    */
  }
  for (int i=0;i<N;i++)
    finalh[i]=lst.query(i,i);
}

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