oj.uz

Submission #577555

# Submission time Handle Problem Language Result Execution time Memory
577555 2022-06-15T04:39:52 Z jack715 Wall (IOI14_wall) C++14
100 / 100
 787 ms 221984 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second

using namespace std;

struct node {
  int mn, mx, st, end;
  node* left;
  node* right;
  node(int MN, int MX, int ST, int END) {
    mn = MN, mx = MX;
    st = ST, end = END;
    left = nullptr;
    right = nullptr;
  };
};

void propogate(node* now) {
  if (now->left == nullptr)
    now->left = new node(0, 0, now->st, (now->st+now->end)/2);
  if (now->right == nullptr)
    now->right = new node(0, 0, (now->st+now->end)/2+1, now->end);
  
  if (now->mx != -1) {
    now->left->mx = max(now->left->mx, now->mx);
    now->right->mx = max(now->right->mx, now->mx);
    if (now->left->mn != -1)
      now->left->mn = max(now->left->mn, now->mx);
    if (now->right->mn != -1)
      now->right->mn = max(now->right->mn, now->mx);
    now->mx = -1;
  } 
  if (now->mn != -1) {
    if (now->left->mn != -1)
      now->left->mn = min(now->left->mn, now->mn);
    else
      now->left->mn = now->mn;

    if (now->right->mn != -1)
      now->right->mn = min(now->right->mn, now->mn);
    else 
      now->right->mn = now->mn;
    
    now->left->mx = min(now->left->mx, now->mn);
    now->right->mx = min(now->right->mx, now->mn);
    now->mn = -1;
  }
}

void update(node* now, int& l, int& r, int& v, int& t) {
  if (now->st > r || now->end < l) 
    return;
  if (l <= now->st && now->end <= r) {
    if (t == 1) {
      now->mx = max(now->mx, v);
      if (now->mn != -1)
        now->mn = max(now->mn, v);
    } else {
      if (now->mn != -1)
        now->mn = min(now->mn, v);
      else
        now->mn = v;
      now->mx = min(now->mx, v);
    }
    return;
  }

  propogate(now);
  update(now->left, l, r, v, t);
  update(now->right, l, r, v, t);
}

vector<int> ans;
void query(node* now) {
  if (now->st == now->end) {
    ans[now->st] = now->mx;
    return;
  }
  propogate(now);
  query(now->left);
  query(now->right);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  node* root = new node(0, 0, 0, n-1);

  for (int i = 0; i < k; i++) {
    update(root, left[i], right[i], height[i], op[i]); 
  }

  ans.resize(n, 0);
  query(root);
  for (int i = 0; i < n; i++)
    finalHeight[i] = ans[i];
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 1432 KB Output is correct
5 Correct 5 ms 1364 KB Output is correct
6 Correct 5 ms 1364 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 129 ms 8112 KB Output is correct
3 Correct 154 ms 5448 KB Output is correct
4 Correct 624 ms 18420 KB Output is correct
5 Correct 265 ms 18988 KB Output is correct
6 Correct 232 ms 19008 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1364 KB Output is correct
5 Correct 5 ms 1364 KB Output is correct
6 Correct 5 ms 1364 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 126 ms 8020 KB Output is correct
9 Correct 167 ms 5440 KB Output is correct
10 Correct 570 ms 18508 KB Output is correct
11 Correct 255 ms 18904 KB Output is correct
12 Correct 235 ms 18900 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 133 ms 8092 KB Output is correct
15 Correct 35 ms 2588 KB Output is correct
16 Correct 681 ms 18968 KB Output is correct
17 Correct 264 ms 18752 KB Output is correct
18 Correct 243 ms 18692 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 9 ms 1444 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 6 ms 1364 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 125 ms 8036 KB Output is correct
9 Correct 160 ms 5436 KB Output is correct
10 Correct 664 ms 18424 KB Output is correct
11 Correct 239 ms 18976 KB Output is correct
12 Correct 235 ms 19020 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 124 ms 8124 KB Output is correct
15 Correct 32 ms 2492 KB Output is correct
16 Correct 644 ms 18704 KB Output is correct
17 Correct 245 ms 18688 KB Output is correct
18 Correct 237 ms 18684 KB Output is correct
19 Correct 757 ms 221932 KB Output is correct
20 Correct 759 ms 219612 KB Output is correct
21 Correct 743 ms 221856 KB Output is correct
22 Correct 758 ms 219376 KB Output is correct
23 Correct 745 ms 219428 KB Output is correct
24 Correct 732 ms 219536 KB Output is correct
25 Correct 737 ms 219556 KB Output is correct
26 Correct 740 ms 221852 KB Output is correct
27 Correct 736 ms 221984 KB Output is correct
28 Correct 737 ms 219348 KB Output is correct
29 Correct 737 ms 219400 KB Output is correct
30 Correct 787 ms 219388 KB Output is correct