oj.uz

Submission #793187

# Submission time Handle Problem Language Result Execution time Memory
793187 2023-07-25T15:33:13 Z Ronin13 Wall (IOI14_wall) C++17
100 / 100
 601 ms 72996 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 2000001;
int l[nmax * 4], r[nmax * 4];


void upd(int a, int b){
    if(l[a] > r[b])
      l[b] = r[b] = l[a];
    else{
      if(r[a] < l[b])
        l[b] = r[b] = r[a];
      else{
          l[b] = max(l[a], l[b]);
          r[b] = min(r[a], r[b]);
      }
    }
}

void push(int v){
  upd(v, 2 * v);
  upd(v, 2 * v + 1);
}

void update(int v, int L, int R, int st, int fin, int val, int op){
  if(L > fin || R < st)
  return;
  if(L >= st && R <= fin){
      if(op == 1){
          l[v] = max(l[v], val);
          r[v] = max(r[v], l[v]);
      }
      else{
          r[v] = min(r[v], val);
          l[v] = min(r[v], l[v]);
      }
      return;
  }
  int m = (L + R) / 2;
  push(v);
  update(2 * v, L, m, st, fin, val, op);
  update(2 * v + 1, m + 1, R, st, fin, val, op);
  l[v] = min(l[2 * v], l[2 * v + 1]);
  r[v] = max(r[2 * v], r[2 * v + 1]);
}
int ans[nmax];
void get(int v, int L, int R){
    if(L == R){
      ans[L] = l[v];
      return;
    }
    int  M = (L + R) / 2;
    push(v);
    get(2 * v, L, M);
    get(2 * v + 1, M + 1, R);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  
  for(int i = 0; i < k; i++){
      update(1, 0, n - 1, left[i], right[i], height[i], op[i]);
  }
  get(1, 0, n - 1);
  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 1 ms 212 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 4 ms 868 KB Output is correct
6 Correct 4 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 104 ms 13200 KB Output is correct
3 Correct 135 ms 7960 KB Output is correct
4 Correct 402 ms 16236 KB Output is correct
5 Correct 235 ms 16820 KB Output is correct
6 Correct 234 ms 16728 KB Output is correct

Subtask #3
29.0 / 29.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 344 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 4 ms 836 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 101 ms 13908 KB Output is correct
9 Correct 138 ms 8052 KB Output is correct
10 Correct 387 ms 17244 KB Output is correct
11 Correct 236 ms 17816 KB Output is correct
12 Correct 234 ms 17760 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 103 ms 13960 KB Output is correct
15 Correct 24 ms 2004 KB Output is correct
16 Correct 416 ms 17500 KB Output is correct
17 Correct 237 ms 17480 KB Output is correct
18 Correct 252 ms 17552 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 5 ms 764 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 101 ms 13840 KB Output is correct
9 Correct 131 ms 7944 KB Output is correct
10 Correct 364 ms 17248 KB Output is correct
11 Correct 243 ms 17756 KB Output is correct
12 Correct 230 ms 17724 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 104 ms 13960 KB Output is correct
15 Correct 23 ms 2016 KB Output is correct
16 Correct 412 ms 17680 KB Output is correct
17 Correct 241 ms 17500 KB Output is correct
18 Correct 236 ms 17476 KB Output is correct
19 Correct 565 ms 72996 KB Output is correct
20 Correct 549 ms 70576 KB Output is correct
21 Correct 546 ms 72996 KB Output is correct
22 Correct 547 ms 70332 KB Output is correct
23 Correct 550 ms 70420 KB Output is correct
24 Correct 546 ms 70220 KB Output is correct
25 Correct 551 ms 70220 KB Output is correct
26 Correct 601 ms 72796 KB Output is correct
27 Correct 554 ms 72408 KB Output is correct
28 Correct 551 ms 69556 KB Output is correct
29 Correct 550 ms 69068 KB Output is correct
30 Correct 545 ms 68640 KB Output is correct