Submission #1326541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326541		anfi	Wall (IOI14_wall)	C++20	100 / 100	488 ms	124200 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
vector<long long> ans;
const int mxn = 2e6;
const long long inf = 1e18;
long long sg[4*mxn+5],mn[4*mxn+5],mx[4*mxn+5],lz[4*mxn+5];

void build(int nd, int l, int r){
  int md = (l+r)>>1;
  if(l == r){
    sg[nd] = -inf;
    return;
  }
  sg[nd] = -inf;
  build(2*nd, l, md), build(2*nd+1, md+1, r);
}

void pro(int nd, int l, int r){
  mx[nd] = mn[nd] = sg[nd];
  if(l < r){
    sg[2*nd] = sg[2*nd+1] = sg[nd];
  }
  sg[nd] = -inf;
}

void bagi(int nd, int l, int r){
  mx[nd] = max(mx[2*nd+1], mx[2*nd]);
  mn[nd] = min(mn[2*nd+1], mn[2*nd]); 
  return;
}

void upd(int nd, int l, int r, int lf, int rg, int v, int op){
  if(op&1){
    if(sg[nd] != -inf) pro(nd, l, r);
    if(l > rg || r < lf || mn[nd] >= v) return;
    if(lf <= l && r <= rg && mn[nd] == mx[nd]){
      sg[nd] = v; pro(nd,l,r);
      return;
    }
    int md = (l+r)>>1;
    upd(2*nd, l, md, lf, rg, v, op);
    upd(2*nd+1, md+1, r, lf, rg, v, op);
    bagi(nd, l, r);
  }else{
    if(sg[nd] != -inf) pro(nd, l, r);
    if(l > rg || r < lf || mx[nd] <= v) return;
    if(lf <= l && r <= rg && mn[nd] == mx[nd]){
      sg[nd] = v; pro(nd,l,r);
      return;
    }
    int md = (l+r)>>1;
    upd(2*nd, l, md, lf, rg, v, op);
    upd(2*nd+1, md+1, r, lf, rg, v, op);
    bagi(nd, l, r);
  }
}

void jawab(int nd, int l, int r){
    if(sg[nd] != -inf) pro(nd,l,r);
    int md = (l+r)>>1;
    if(mx[nd] == mn[nd]){
        for(int i = l; i <= r; i++) ans[i] = mx[nd];
        return;
    }
    jawab(2*nd,l,md);
    jawab(2*nd+1,md+1,r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  ans = vector<long long>(n+1, 0);
  build(1,0,n-1);
  for(int i = 0; i < k; i++){
    if(op[i]&1){
      upd(1,0,n-1,left[i],right[i],height[i],op[i]);
    }else{
      upd(1,0,n-1,left[i],right[i],height[i],op[i]);
    }
  }
  jawab(1,0,n-1);
  for(int i = 0; i < n; i++)finalHeight[i] = ans[i];
  return;
}
/*
int main(){
  int n,k; cin >> n >> k;
  int op[k],left[k],right[k],height[k],finalheight[n];
  for(int i = 0; i < k; i++) cin >> op[i] >> left[i] >> right[i] >> height[i];
  buildWall(n,k,op,left,right,height,finalheight);
  for(int i = 0; i < n; i++) cout << ans[i] << ' ';
}*/

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