oj.uz

Submission #173006

# Submission time Handle Problem Language Result Execution time Memory
173006 2020-01-03T01:05:17 Z Nightlight Wall (IOI14_wall) C++14
100 / 100
 649 ms 72884 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define adds 1
#define remov 2
#define left(n) (n<<1)
#define right(n) (n<<1|1)
using namespace std;

const int last = 1 << 21;
const int szt = 5e6;
const int maxn = 1<<21;
const int inf = 0x3f3f3f3f;

int ql, qr, state, val; 

struct segtree{
  int mx[szt], mn[szt];
  segtree() {
    memset(mx, inf, sizeof(mx));
  }
  void go(int node) {
    if(state == 2) {
      mx[node] = min(mx[node], val);
      mn[node] = min(mn[node], val);
    }else {
      mx[node] = max(mx[node], val);
      mn[node] = max(mn[node], val);
    }
  }
  void merge(int par, int kid) {
    mx[kid] = min(mx[kid], mx[par]);
    mx[kid] = max(mx[kid], mn[par]);
    mn[kid] = max(mn[kid], mn[par]);
    mn[kid] = min(mn[kid], mx[par]);
  }
  void unlazy(int node) {
    merge(node, left(node));
    merge(node, right(node));
    mx[node] = inf; mn[node] = 0;
  }
  void update(int node, int l, int r) {
    if(ql <= l && r <= qr) {
      go(node);
      return;
    }
    unlazy(node);
    int mid = (l + r) >> 1;
    if(ql <= mid) update(left(node), l, mid);
    if(qr > mid) update(right(node), mid + 1, r);
  }
  void finish() {
    for(int i = 1; i < last; i++)unlazy(i);
  }
};

segtree tree;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int ans[]){
  for(int i = 0; i < k; i++) {
    state = op[i], ql = left[i] + 1, qr = right[i] + 1, val = height[i];
//    cout << state << " " << ql << " " << qr << " " << val << "\n";
    tree.update(1, 1, last);
  }
  tree.finish();
  int cnt = 0;
  for(int i = last; i < last + n; i++) {
//    ans[cnt++] = tree.mn[i];
    ans[cnt++] = min(tree.mx[i], tree.mn[i]);
  }
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 36344 KB Output is correct
2 Correct 51 ms 36472 KB Output is correct
3 Correct 58 ms 36348 KB Output is correct
4 Correct 53 ms 36600 KB Output is correct
5 Correct 58 ms 36600 KB Output is correct
6 Correct 54 ms 36572 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 36344 KB Output is correct
2 Correct 325 ms 50084 KB Output is correct
3 Correct 227 ms 43612 KB Output is correct
4 Correct 525 ms 54400 KB Output is correct
5 Correct 341 ms 55428 KB Output is correct
6 Correct 329 ms 53880 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 36336 KB Output is correct
2 Correct 51 ms 36440 KB Output is correct
3 Correct 56 ms 36472 KB Output is correct
4 Correct 53 ms 36600 KB Output is correct
5 Correct 53 ms 36600 KB Output is correct
6 Correct 52 ms 36600 KB Output is correct
7 Correct 48 ms 36344 KB Output is correct
8 Correct 330 ms 50044 KB Output is correct
9 Correct 225 ms 43512 KB Output is correct
10 Correct 525 ms 54380 KB Output is correct
11 Correct 342 ms 55532 KB Output is correct
12 Correct 330 ms 53984 KB Output is correct
13 Correct 48 ms 36344 KB Output is correct
14 Correct 329 ms 50012 KB Output is correct
15 Correct 76 ms 37496 KB Output is correct
16 Correct 527 ms 54776 KB Output is correct
17 Correct 335 ms 54192 KB Output is correct
18 Correct 334 ms 54012 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 36344 KB Output is correct
2 Correct 50 ms 36432 KB Output is correct
3 Correct 52 ms 36344 KB Output is correct
4 Correct 52 ms 36604 KB Output is correct
5 Correct 51 ms 36600 KB Output is correct
6 Correct 52 ms 36600 KB Output is correct
7 Correct 47 ms 36344 KB Output is correct
8 Correct 326 ms 50040 KB Output is correct
9 Correct 224 ms 43640 KB Output is correct
10 Correct 525 ms 54428 KB Output is correct
11 Correct 345 ms 55532 KB Output is correct
12 Correct 331 ms 53872 KB Output is correct
13 Correct 48 ms 36344 KB Output is correct
14 Correct 328 ms 50040 KB Output is correct
15 Correct 76 ms 37496 KB Output is correct
16 Correct 541 ms 54776 KB Output is correct
17 Correct 340 ms 53908 KB Output is correct
18 Correct 337 ms 54136 KB Output is correct
19 Correct 649 ms 72812 KB Output is correct
20 Correct 644 ms 70396 KB Output is correct
21 Correct 648 ms 72884 KB Output is correct
22 Correct 636 ms 70160 KB Output is correct
23 Correct 633 ms 70280 KB Output is correct
24 Correct 633 ms 70268 KB Output is correct
25 Correct 631 ms 70360 KB Output is correct
26 Correct 643 ms 72736 KB Output is correct
27 Correct 647 ms 72748 KB Output is correct
28 Correct 632 ms 70264 KB Output is correct
29 Correct 634 ms 70304 KB Output is correct
30 Correct 641 ms 70440 KB Output is correct