oj.uz

Submission #841726

# Submission time Handle Problem Language Result Execution time Memory
841726 2023-09-02T01:15:02 Z 12345678 Wall (IOI14_wall) C++17
0 / 100
 162 ms 78164 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=2e6+5;

struct segtree
{
  int ans[nx];
  struct node
  {
    int low, up;
    node(): low(INT_MIN), up(INT_MAX){}
  } d[4*nx];
  void change(int nw, int p)
  {
    d[nw].low=max(d[nw].low, d[p].low);
    d[nw].low=min(d[nw].low, d[p].up);
    d[nw].up=min(d[nw].up, d[p].up);
    d[nw].up=max(d[nw].up, d[p].low);
  }
  void pushlz(int l, int r, int i)
  {
    if (l==r) return;
    change(2*i, i);
    change(2*i+1, i);
    d[i].low=INT_MIN; d[i].up=INT_MAX;
  }
  void add(int l, int r, int i, int ql, int qr, int t)
  {
    pushlz(l, r, i);
    if (qr<l||r<ql) return;
    if (ql<=l&&r<=qr) return d[i].low=t, d[i].up=max(d[i].low, d[i].up), void();
    int md=(l+r)/2;
    add(l, md, 2*i, ql, qr, t);
    add(md+1, r, 2*i+1, ql, qr, t);
    //d[i].low=min(d[i].low, d[i].up);
    //d[i].up=max(d[i].up, d[i].low);
  }
  void remove(int l, int r, int i, int ql, int qr, int t)
  {
    pushlz(l, r, i);
    if (qr<l||r<ql) return;
    if (ql<=l&&r<=qr) return d[i].up=t, d[i].low=min(d[i].low, d[i].up), void();
    int md=(l+r)/2;
    remove(l, md, 2*i, ql, qr, t);
    remove(md+1, r, 2*i+1, ql, qr, t);
  }
  /*
  void show(int l, int r, int i)
  {
    cout<<l<<' '<<r<<' '<<i<<' '<<d[i].low<<' '<<d[i].up<<'\n';
    if (l==r) return;
    show(l, (l+r)/2, 2*i);
    show((l+r)/2+1, r, 2*i+1);
  }*/
  void dfs(int l, int r, int i)
  {
    pushlz(l, r, i);
    if (l==r)
    {
      ans[l]=max(d[i].low, 0);
      return;
    }
    int md=(l+r)/2;
    dfs(l, md, 2*i);
    dfs(md+1, r, 2*i+1);
  }
} s;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for (int i=0; i<k; i++)
  {
    if (op[i]==1) s.add(0, n-1, 1, left[i], right[i], height[i]);
    else s.remove(0, n-1, 1, left[i], right[i], height[i]);
  }
  s.dfs(0, n-1, 1);
  for (int i=0; i<n; i++) finalHeight[i]=s.ans[i];
  return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 64348 KB Output is correct
2 Correct 13 ms 64604 KB Output is correct
3 Incorrect 14 ms 64604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 64600 KB Output is correct
2 Correct 123 ms 78164 KB Output is correct
3 Incorrect 162 ms 71548 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 64348 KB Output is correct
2 Correct 13 ms 64604 KB Output is correct
3 Incorrect 13 ms 64604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 64480 KB Output is correct
2 Correct 13 ms 64604 KB Output is correct
3 Incorrect 13 ms 64604 KB Output isn't correct
4 Halted 0 ms 0 KB -