Submission #342017

#	Time	Username	Problem	Language	Result	Execution time	Memory
342017		MilosMilutinovic	Wall (IOI14_wall)	C++14	100 / 100	987 ms	94112 KiB

wall

/**
 *  author: milos
 *  created: 01.01.2021 04:18:07
**/
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 5e6 + 5;

struct segtree{
  int mn[N], mx[N], a[N];
  void build(int c, int x, int y) {
    if (mn[c] == 1e9) {
      return;  
    }
    mn[c] = 1e9, mx[c] = 0, a[c] = 0;
    if (x >= y) {
      return;
    }
    int mid = x + y >> 1;
    build(c * 2 + 1, x, mid);
    build(c * 2 + 2, mid + 1, y);
  }
  void push(int c, int x, int y) {
    a[c] = max(a[c], mx[c]);
    a[c] = min(a[c], mn[c]);
    if (x != y) {
      mx[2 * c + 1] = max(mx[c * 2 + 1], mx[c]);
      mx[2 * c + 1] = min(mx[c * 2 + 1], mn[c]);
      mn[2 * c + 1] = max(mn[c * 2 + 1], mx[c]);
      mn[2 * c + 1] = min(mn[c * 2 + 1], mn[c]);
      mx[2 * c + 2] = max(mx[c * 2 + 2], mx[c]);
      mx[2 * c + 2] = min(mx[c * 2 + 2], mn[c]);
      mn[2 * c + 2] = max(mn[c * 2 + 2], mx[c]);
      mn[2 * c + 2] = min(mn[c * 2 + 2], mn[c]); 
    }
    mn[c] = 1e9, mx[c] = 0;
  }
  void add(int c, int x, int y, int l, int r, int val) {
    push(c, x, y);
    if (x > y || x > r || y < l) {
      return;
    }
    if (x >= l && y <= r) {
      mx[c] = val;
      return;
    }
    int mid = x + y >> 1;
    add(c * 2 + 1, x, mid, l, r, val);
    add(c * 2 + 2, mid + 1, y, l, r, val);
  }
  void del(int c, int x, int y, int l, int r, int val) {
    push(c, x, y);
    if (x > y || x > r || y < l) {
      return;
    }
    if (x >= l && y <= r) {
      mn[c] = val;
      return;
    }
    int mid = x + y >> 1;
    del(c * 2 + 1, x, mid, l, r, val);
    del(c * 2 + 2, mid + 1, y, l, r, val);
  }           
} st;

vector<int> ans;

void Solve(int c, int l, int r) {
  if (l > r) {
    return;
  }
  st.push(c, l, r);
  if (l == r) {
    ans.push_back(st.a[c]);
    return;
  }  
  int mid = l + r >> 1;
  Solve(c * 2 + 1, l, mid);
  Solve(c * 2 + 2, mid + 1, r);
}

void buildWall(int n, int q, int* op, int* left, int* right, int* height, int* finalHeight) {
  st.build(0, 0, n - 1);
  for (int i = 0; i < q; i++) {
    if (op[i] == 1) {
      st.add(0, 0, n - 1, left[i], right[i], height[i]); 
    } else {
      st.del(0, 0, n - 1, left[i], right[i], height[i]); 
    }
  }
  Solve(0, 0, n - 1);
  for (int i = 0; i < n; i++) {
    finalHeight[i] = ans[i];
  }
}

Compilation message (stderr)

wall.cpp: In member function 'void segtree::build(int, int, int)':
wall.cpp:22:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     int mid = x + y >> 1;
      |               ~~^~~
wall.cpp: In member function 'void segtree::add(int, int, int, int, int, int)':
wall.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int mid = x + y >> 1;
      |               ~~^~~
wall.cpp: In member function 'void segtree::del(int, int, int, int, int, int)':
wall.cpp:63:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int mid = x + y >> 1;
      |               ~~^~~
wall.cpp: In function 'void Solve(int, int, int)':
wall.cpp:80:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |   int mid = l + r >> 1;
      |             ~~^~~

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