oj.uz

Submission #666595

# Submission time Handle Problem Language Result Execution time Memory
666595 2022-11-29T06:41:22 Z atigun Wall (IOI14_wall) C++11
100 / 100
 662 ms 79688 KB 
#include<bits/stdc++.h>
#include"wall.h"

using namespace std;
typedef long long ll;

struct segtree{
  struct node{
    int min_opt, max_opt;
    node() : min_opt(1e9), max_opt(0){}
  };
  vector<node> tree;
  int N;
  segtree(const int& treesize) : N(treesize){
    tree.resize(4*N+5);
  }
  void push(int v, bool side){
    int where = (side ? v*2+1 : v*2);
    if(tree[v].min_opt != 1e9){
      tree[where].min_opt = min(tree[where].min_opt, tree[v].min_opt);
      tree[where].max_opt = min(tree[where].max_opt, tree[where].min_opt);
      if(side)
        tree[v].min_opt = 1e9;
    }
    if(tree[v].max_opt != 0){
      tree[where].max_opt = max(tree[where].max_opt, tree[v].max_opt);
      tree[where].min_opt = max(tree[where].min_opt, tree[where].max_opt);
      if(side)
        tree[v].max_opt = 0;
    }
  }
  void max_update(int v, int l, int r, int L, int R, int D){
    if(l > R || r < L){
      return;
    }
    if(r <= R && l >= L){
      tree[v].max_opt = max(tree[v].max_opt, D);
      tree[v].min_opt = max(tree[v].min_opt, tree[v].max_opt);
      return;
    }
    push(v, 0);
    push(v, 1);
    int mid = (l+r)/2;
    max_update(v*2, l, mid, L, R, D);
    max_update(v*2+1, mid+1, r, L, R, D);
  }
  void min_update(int v, int l, int r, int L, int R, int D){
    if(l > R || r < L){
      return;
    }
    if(r <= R && l >= L){
      tree[v].min_opt = min(tree[v].min_opt, D);
      tree[v].max_opt = min(tree[v].max_opt, tree[v].min_opt);
      return;
    }
    push(v, 0);
    push(v, 1);
    int mid = (l+r)/2;
    min_update(v*2, l, mid, L, R, D);
    min_update(v*2+1, mid+1, r, L, R, D);
  }
  void max_update(int L, int R, int D){
    max_update(1, 0, N, L, R, D);
  }
  void min_update(int L, int R, int D){
    min_update(1, 0, N, L, R, D);
  }
  int get(int v, int l, int r, int I){
    if(l == r)
      return max(min(0, tree[v].min_opt), tree[v].max_opt);
    push(v, 0);
    push(v, 1);
    int mid = (l+r)/2;
    if(I <= mid)
      return get(v*2, l, mid, I);
    else
      return get(v*2+1, mid+1, r, I);
  }
  int operator[](int I){
    return get(1, 0, N, I);
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  segtree ST(n);
  for(int i = 0; i < k; i++){
    if(op[i] == 1){
      ST.max_update(left[i], right[i], height[i]);
    } else{
      ST.min_update(left[i], right[i], height[i]);
    }
  }
  for(int i = 0; i < n; i++)
    finalHeight[i] = ST[i];
}

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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 134 ms 8204 KB Output is correct
3 Correct 131 ms 4236 KB Output is correct
4 Correct 361 ms 11708 KB Output is correct
5 Correct 213 ms 12648 KB Output is correct
6 Correct 214 ms 12592 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 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 5 ms 756 KB Output is correct
5 Correct 5 ms 824 KB Output is correct
6 Correct 4 ms 756 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 134 ms 8168 KB Output is correct
9 Correct 130 ms 4300 KB Output is correct
10 Correct 378 ms 12676 KB Output is correct
11 Correct 204 ms 12616 KB Output is correct
12 Correct 203 ms 12768 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 126 ms 9056 KB Output is correct
15 Correct 24 ms 1912 KB Output is correct
16 Correct 419 ms 12800 KB Output is correct
17 Correct 213 ms 12616 KB Output is correct
18 Correct 227 ms 12672 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 2 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 140 ms 8172 KB Output is correct
9 Correct 128 ms 4304 KB Output is correct
10 Correct 334 ms 12780 KB Output is correct
11 Correct 218 ms 12620 KB Output is correct
12 Correct 222 ms 12756 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 134 ms 9088 KB Output is correct
15 Correct 27 ms 1904 KB Output is correct
16 Correct 421 ms 12668 KB Output is correct
17 Correct 238 ms 12636 KB Output is correct
18 Correct 206 ms 12588 KB Output is correct
19 Correct 656 ms 79592 KB Output is correct
20 Correct 637 ms 79564 KB Output is correct
21 Correct 643 ms 79592 KB Output is correct
22 Correct 652 ms 79508 KB Output is correct
23 Correct 658 ms 79584 KB Output is correct
24 Correct 644 ms 79592 KB Output is correct
25 Correct 647 ms 79564 KB Output is correct
26 Correct 662 ms 79676 KB Output is correct
27 Correct 645 ms 79596 KB Output is correct
28 Correct 658 ms 79564 KB Output is correct
29 Correct 628 ms 79544 KB Output is correct
30 Correct 620 ms 79688 KB Output is correct