oj.uz

Submission #647633

# Submission time Handle Problem Language Result Execution time Memory
647633 2022-10-03T11:15:02 Z alvinpiter Wall (IOI14_wall) C++17
100 / 100
 883 ms 99344 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define MAXN 2000000

struct Node {
  int mini, maxi;
  Node(int mini_ = 0, int maxi_ = INF): mini(mini_), maxi(maxi_) {}
};

int N;
Node lazy[4 * MAXN + 3];

void pushDown(int nodeNum) {
  lazy[2 * nodeNum] = Node(
    min(lazy[nodeNum].maxi, max(lazy[2 * nodeNum].mini, lazy[nodeNum].mini)),
    max(lazy[nodeNum].mini, min(lazy[2 * nodeNum].maxi, lazy[nodeNum].maxi))
  );

  lazy[2 * nodeNum + 1] = Node(
    min(lazy[nodeNum].maxi, max(lazy[2 * nodeNum + 1].mini, lazy[nodeNum].mini)),
    max(lazy[nodeNum].mini, min(lazy[2 * nodeNum + 1].maxi, lazy[nodeNum].maxi))
  );

  lazy[nodeNum] = Node(0, INF);
}

void doUpdate(int nodeNum, int l, int r, int type, int ql, int qr, int val) {
  if (qr < l || ql > r) {
    return;
  }

  if (l >= ql && r <= qr) {
    if (type == 1) {
      // "at least val"
      lazy[nodeNum].mini = max(lazy[nodeNum].mini, val);
      lazy[nodeNum].maxi = max(lazy[nodeNum].maxi, val);
    } else if (type == 2) {
      // "at most val"
      lazy[nodeNum].mini = min(lazy[nodeNum].mini, val);
      lazy[nodeNum].maxi = min(lazy[nodeNum].maxi, val);
    }

    return;
  }

  pushDown(nodeNum);

  int m = (l + r)/2;
  doUpdate(2 * nodeNum, l, m, type, ql, qr, val);
  doUpdate(2 * nodeNum + 1, m + 1, r, type, ql, qr, val);
}

void update(int type, int ql, int qr, int val) {
  doUpdate(1, 1, N, type, ql, qr, val);
}

int doQuery(int nodeNum, int l, int r, int idx) {
  if (l == r) {
    return lazy[nodeNum].mini;
  }

  pushDown(nodeNum);

  int m = (l + r)/2;
  if (idx <= m) {
    return doQuery(2 * nodeNum, l, m, idx);
  } else {
    return doQuery(2 * nodeNum + 1, m + 1, r, idx);
  }
}

int query(int idx) {
  return doQuery(1, 1, N, idx);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N = n;

  // Initialize tree
  for (int i = 1; i <= 4 * N; i++) {
    lazy[i] = Node(0, INF);
  }

  for (int i = 0; i < k; i++) {
    update(op[i], left[i] + 1, right[i] + 1, height[i]);
    // cout << "\nlazy after op " << i << endl;
    // for (int j = 1; j <= 3; j++) {
    //   cout << "hehe " << j << " " << lazy[j].mini << " " << lazy[j].maxi << endl;
    // }
  }

  for (int i = 0; i < n; i++) {
    finalHeight[i] = query(i + 1);
    // cout << "\nlazy after query " << i << endl;
    // for (int j = 1; j <= 3; j++) {
    //   cout << "hehe " << j << " " << lazy[j].mini << " " << lazy[j].maxi << endl;
    // }
  }

  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62780 KB Output is correct
2 Correct 29 ms 62956 KB Output is correct
3 Correct 28 ms 62932 KB Output is correct
4 Correct 34 ms 63128 KB Output is correct
5 Correct 31 ms 63132 KB Output is correct
6 Correct 32 ms 63084 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62804 KB Output is correct
2 Correct 159 ms 70736 KB Output is correct
3 Correct 159 ms 66288 KB Output is correct
4 Correct 396 ms 71348 KB Output is correct
5 Correct 275 ms 71780 KB Output is correct
6 Correct 292 ms 71776 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 62908 KB Output is correct
2 Correct 32 ms 62932 KB Output is correct
3 Correct 31 ms 62812 KB Output is correct
4 Correct 33 ms 63100 KB Output is correct
5 Correct 33 ms 63064 KB Output is correct
6 Correct 35 ms 63104 KB Output is correct
7 Correct 30 ms 62800 KB Output is correct
8 Correct 170 ms 76460 KB Output is correct
9 Correct 165 ms 70092 KB Output is correct
10 Correct 427 ms 80944 KB Output is correct
11 Correct 301 ms 81996 KB Output is correct
12 Correct 292 ms 80420 KB Output is correct
13 Correct 30 ms 62968 KB Output is correct
14 Correct 174 ms 76520 KB Output is correct
15 Correct 54 ms 64092 KB Output is correct
16 Correct 419 ms 81224 KB Output is correct
17 Correct 290 ms 80528 KB Output is correct
18 Correct 290 ms 80552 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 62804 KB Output is correct
2 Correct 29 ms 62872 KB Output is correct
3 Correct 30 ms 62924 KB Output is correct
4 Correct 34 ms 63088 KB Output is correct
5 Correct 33 ms 63052 KB Output is correct
6 Correct 33 ms 63048 KB Output is correct
7 Correct 29 ms 62832 KB Output is correct
8 Correct 174 ms 76476 KB Output is correct
9 Correct 160 ms 70012 KB Output is correct
10 Correct 407 ms 80884 KB Output is correct
11 Correct 287 ms 81992 KB Output is correct
12 Correct 284 ms 80372 KB Output is correct
13 Correct 29 ms 62856 KB Output is correct
14 Correct 169 ms 76556 KB Output is correct
15 Correct 54 ms 64036 KB Output is correct
16 Correct 459 ms 81204 KB Output is correct
17 Correct 289 ms 80580 KB Output is correct
18 Correct 296 ms 80568 KB Output is correct
19 Correct 874 ms 99216 KB Output is correct
20 Correct 868 ms 96760 KB Output is correct
21 Correct 881 ms 99344 KB Output is correct
22 Correct 864 ms 96788 KB Output is correct
23 Correct 859 ms 96716 KB Output is correct
24 Correct 860 ms 96808 KB Output is correct
25 Correct 861 ms 96844 KB Output is correct
26 Correct 877 ms 99240 KB Output is correct
27 Correct 857 ms 99344 KB Output is correct
28 Correct 862 ms 96848 KB Output is correct
29 Correct 861 ms 96708 KB Output is correct
30 Correct 883 ms 96716 KB Output is correct