oj.uz

Submission #841738

# Submission time Handle Problem Language Result Execution time Memory
841738 2023-09-02T01:46:04 Z 12345678 Wall (IOI14_wall) C++17
100 / 100
 552 ms 99464 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=2e6+5;

struct segtree
{
  struct node
  {
    int low, up;
    node(): low(0), up(INT_MAX){}
  } d[4*nx];
  void add(int l, int r, int i, int ql, int qr, int t)
  {
    if (qr<l||r<ql) return;
    t=max(t, d[i].low);
    t=min(t, d[i].up);
    if (ql<=l&&r<=qr) return void(d[i].low=t);
    int md=(l+r)/2;
    add(l, md, 2*i, ql, qr, t);
    add(md+1, r, 2*i+1, ql, qr, t);
  }
  void remove(int l, int r, int i, int ql, int qr, int t)
  {
    if (qr<l||r<ql) return;
    t=max(t, d[i].low);
    t=min(t, d[i].up);
    if (ql<=l&&r<=qr) return void(d[i].up=t);
    int md=(l+r)/2;
    remove(l, md, 2*i, ql, qr, t);
    remove(md+1, r, 2*i+1, ql, qr, t);
  }
  int query(int l, int r, int i, int idx, int t)
  {
    t=max(t, d[i].low);
    t=min(t, d[i].up);
    if (l==r) return t;
    int md=(l+r)/2;
    if (idx<=md) return query(l, md, 2*i, idx, t);
    else return query(md+1, r, 2*i+1, idx, t);
  }
} s;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for (int i=k-1; i>=0; 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]);
  }
  for (int i=0; i<n; i++) finalHeight[i]=s.query(0, n-1, 1, i, 0);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 62812 KB Output is correct
2 Correct 13 ms 63068 KB Output is correct
3 Correct 12 ms 63068 KB Output is correct
4 Correct 15 ms 63328 KB Output is correct
5 Correct 16 ms 63068 KB Output is correct
6 Correct 14 ms 63068 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 62812 KB Output is correct
2 Correct 118 ms 70832 KB Output is correct
3 Correct 107 ms 66368 KB Output is correct
4 Correct 300 ms 81152 KB Output is correct
5 Correct 199 ms 81976 KB Output is correct
6 Correct 179 ms 80536 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 63068 KB Output is correct
2 Correct 12 ms 62904 KB Output is correct
3 Correct 12 ms 63068 KB Output is correct
4 Correct 16 ms 63068 KB Output is correct
5 Correct 15 ms 63172 KB Output is correct
6 Correct 15 ms 63124 KB Output is correct
7 Correct 11 ms 62824 KB Output is correct
8 Correct 115 ms 76688 KB Output is correct
9 Correct 108 ms 70128 KB Output is correct
10 Correct 289 ms 81028 KB Output is correct
11 Correct 188 ms 82048 KB Output is correct
12 Correct 182 ms 80532 KB Output is correct
13 Correct 11 ms 62812 KB Output is correct
14 Correct 121 ms 76644 KB Output is correct
15 Correct 30 ms 64092 KB Output is correct
16 Correct 290 ms 81216 KB Output is correct
17 Correct 188 ms 80724 KB Output is correct
18 Correct 191 ms 80724 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 62808 KB Output is correct
2 Correct 18 ms 62924 KB Output is correct
3 Correct 36 ms 62904 KB Output is correct
4 Correct 19 ms 63072 KB Output is correct
5 Correct 15 ms 63180 KB Output is correct
6 Correct 14 ms 63068 KB Output is correct
7 Correct 12 ms 62848 KB Output is correct
8 Correct 111 ms 76600 KB Output is correct
9 Correct 109 ms 70228 KB Output is correct
10 Correct 281 ms 81048 KB Output is correct
11 Correct 184 ms 81948 KB Output is correct
12 Correct 209 ms 80536 KB Output is correct
13 Correct 12 ms 62812 KB Output is correct
14 Correct 115 ms 76652 KB Output is correct
15 Correct 28 ms 64092 KB Output is correct
16 Correct 299 ms 81316 KB Output is correct
17 Correct 210 ms 80720 KB Output is correct
18 Correct 183 ms 80640 KB Output is correct
19 Correct 538 ms 99464 KB Output is correct
20 Correct 533 ms 96968 KB Output is correct
21 Correct 542 ms 99264 KB Output is correct
22 Correct 539 ms 96876 KB Output is correct
23 Correct 531 ms 96968 KB Output is correct
24 Correct 547 ms 97108 KB Output is correct
25 Correct 540 ms 96696 KB Output is correct
26 Correct 550 ms 99248 KB Output is correct
27 Correct 527 ms 99416 KB Output is correct
28 Correct 537 ms 96796 KB Output is correct
29 Correct 552 ms 96888 KB Output is correct
30 Correct 539 ms 97084 KB Output is correct