oj.uz

Submission #1086228

# Submission time Handle Problem Language Result Execution time Memory
1086228 2024-09-09T18:18:41 Z belgianbot Wall (IOI14_wall) C++17
100 / 100
 794 ms 169916 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

vector<pair <pair <int,int>, pair<int,int> > > t;
void add(int i, int h, int ph){
  if (i == 24) {
    cin.tie(0);
  }
  if (t[i].se.se == -1) {
    t[i].se = {h, ph};
    return;
  }
  if (t[i].se.se != ph) {
    swap(t[i].fi, t[i].se);
    if (ph == 1) {
      t[i].se.fi = min(t[i].se.fi, t[i].fi.fi);
    }
    else t[i].se.fi = max(t[i].se.fi, t[i].fi.fi);
  }
  if (ph == 1) t[i].se.fi = max(t[i].se.fi, h);
  else t[i].se.fi = t[i].se.se == -1 ? h : min(t[i].se.fi, h);
  t[i].se.se = ph;
}
void merge(int i){
  
  if (t[i].fi.se != -1) {
    add(i * 2, t[i].fi.fi, t[i].fi.se);
    add(i * 2 + 1, t[i].fi.fi, t[i].fi.se);
  }
  if (t[i].se.se != -1) {
    add(i * 2, t[i].se.fi, t[i].se.se);
    add(i * 2 + 1, t[i].se.fi, t[i].se.se);
  }
  t[i] = { {0, -1}, {0, -1}};
}
void update(int i, int l, int r, int Ql, int Qr, int h, int ph) {
  if (l != r) merge(i);
  if (l > Qr || r < Ql) return;
  if (l >= Ql && r <= Qr) {
    add(i, h, ph);
    return;
  }
  
  int mid = (l + r) / 2;
  update(i * 2, l, mid, Ql, Qr, h, ph);
  update(i * 2 + 1, mid + 1, r, Ql, Qr, h, ph);
}

vector<int> ans;

void Query(int i, int l, int r) {
  if (l == r) {
    auto x = t[i];
    if (x.se.se == 1) ans[l] = x.se.fi;
    else ans[l] = min(x.fi.fi, x.se.fi);
    return;
  }
  int mid = (l + r) / 2;

  merge(i);
  Query(i * 2, l, mid);
  Query(i * 2 + 1, mid + 1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  
  t.resize(4 * n , { {0, -1}, {0, -1}}); ans.resize(n);
  for (int i = 0; i < k; i++) update(1, 0, n - 1, left[i], right[i], height[i], op[i]);

  Query(1, 0, n-1);
  for (int i = 0; i < n; i++) {
    finalHeight[i] = ans[i];
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 7 ms 1116 KB Output is correct
5 Correct 4 ms 1368 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 81 ms 13836 KB Output is correct
3 Correct 189 ms 8552 KB Output is correct
4 Correct 558 ms 24912 KB Output is correct
5 Correct 191 ms 25936 KB Output is correct
6 Correct 184 ms 24508 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 7 ms 1320 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 80 ms 13944 KB Output is correct
9 Correct 190 ms 8748 KB Output is correct
10 Correct 545 ms 24912 KB Output is correct
11 Correct 193 ms 25936 KB Output is correct
12 Correct 185 ms 24372 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 83 ms 13936 KB Output is correct
15 Correct 40 ms 2672 KB Output is correct
16 Correct 794 ms 25200 KB Output is correct
17 Correct 202 ms 24656 KB Output is correct
18 Correct 203 ms 24916 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 7 ms 1316 KB Output is correct
5 Correct 4 ms 1368 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 83 ms 13964 KB Output is correct
9 Correct 196 ms 8788 KB Output is correct
10 Correct 571 ms 25116 KB Output is correct
11 Correct 189 ms 26096 KB Output is correct
12 Correct 183 ms 24388 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 83 ms 13840 KB Output is correct
15 Correct 44 ms 2652 KB Output is correct
16 Correct 770 ms 25268 KB Output is correct
17 Correct 198 ms 24640 KB Output is correct
18 Correct 202 ms 24656 KB Output is correct
19 Correct 552 ms 169812 KB Output is correct
20 Correct 558 ms 167160 KB Output is correct
21 Correct 543 ms 169916 KB Output is correct
22 Correct 559 ms 167332 KB Output is correct
23 Correct 557 ms 167408 KB Output is correct
24 Correct 562 ms 167372 KB Output is correct
25 Correct 575 ms 167252 KB Output is correct
26 Correct 582 ms 169704 KB Output is correct
27 Correct 561 ms 169780 KB Output is correct
28 Correct 542 ms 167368 KB Output is correct
29 Correct 581 ms 167308 KB Output is correct
30 Correct 565 ms 167248 KB Output is correct