Submission #959642

#	Time	Username	Problem	Language	Result	Execution time	Memory
959642		vjudge1	Wall (IOI14_wall)	C++17	32 / 100	3095 ms	19216 KiB

wall

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e6, inf = INT_MAX;
 
struct node {
  int mx, mn;
};
 
int n, lazMx[N*4], lazMn[N*4];
node seg[N*4];
 
void build(int p=1, int l=0, int r=n-1) {
  if (l == r) {
    seg[p].mx = 0;
    seg[p].mn = 0;
    return;
  }
  int mid = (l+r) >> 1;
  seg[p].mx = seg[p].mn = 0;
}
 
void updateMx(int a, int b, int c, int p=1, int l=0, int r=n-1) {
  if (seg[p].mn >= c) return;
  else if (l == r) {
    seg[p].mx = max(seg[p].mx, c);
    seg[p].mn = max(seg[p].mn, c); 
    return;
  }
  int mid = (l+r) >> 1;
  if (a <= mid) updateMx(a, b, c, p*2, l, mid);
  if (mid+1 <= b) updateMx(a, b, c, p*2+1, mid+1, r);
  seg[p].mx = max(seg[p*2].mx, seg[p*2+1].mx);
  seg[p].mn = min(seg[p*2].mn, seg[p*2+1].mn);
}
 
void updateMn(int a, int b, int c, int p=1, int l=0, int r=n-1) {
  if (seg[p].mx <= c) return;
  else if (l == r) {
    seg[p].mx = min(seg[p].mx, c);
    seg[p].mn = min(seg[p].mn, c); 
    return;
  }
  int mid = (l+r) >> 1;
  if (a <= mid) updateMn(a, b, c, p*2, l, mid);
  if (mid+1 <= b) updateMn(a, b, c, p*2+1, mid+1, r);
  seg[p].mx = max(seg[p*2].mx, seg[p*2+1].mx);
  seg[p].mn = min(seg[p*2].mn, seg[p*2+1].mn);
}
 
int query(int a, int p=1, int l=0, int r=n-1) {
  if (l == r) {
    return seg[p].mx;
  }
  //pushDown(p);
  int mid = (l+r) >> 1;
  if (a <= mid) return query(a, p*2, l, mid);
  else return query(a, p*2+1, mid+1, r);
}
 
void buildWall(int NN, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  n = NN;
 
  build();
  for (int i = 0; i < k; i++) {
    if (op[i] == 1) updateMx(left[i], right[i], height[i]);
    else updateMn(left[i], right[i], height[i]);
  }
 
  for (int i = 0; i < n; i++) {
    finalHeight[i] = query(i);
  }
}

Compilation message (stderr)

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:22:7: warning: unused variable 'mid' [-Wunused-variable]
   22 |   int mid = (l+r) >> 1;
      |       ^~~

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