oj.uz

Submission #50671

# Submission time Handle Problem Language Result Execution time Memory
50671 2018-06-12T12:48:13 Z Talant Wall (IOI14_wall) C++17
100 / 100
 866 ms 201476 KB 
#include "wall.h"

#include <bits/stdc++.h>

#define pb push_back
#define fr first
#define sc second
#define mk make_pair

using namespace std;

const int N = (int) 2e6 + 6;

int nn;

struct node {
      int mn,mx;
      node () {
            mx = 0,mn = 1e6 + 5;
      }
}t[N * 4];

void upd (int tp,int v,int h) {
      if (tp == 1) {
            t[v].mx = max(t[v].mx,h);
            t[v].mn = max(t[v].mn,h);
      }
      else {
            t[v].mn = min(t[v].mn,h);
            t[v].mx = min(t[v].mx,h);
      }
}
void push(int v) {
      upd(1,v + v,t[v].mx);
      upd(2,v + v,t[v].mn);
      upd(1,v + v + 1,t[v].mx);
      upd(2,v + v + 1,t[v].mn);

      t[v].mx = 0,t[v].mn = 1e6 + 5;
}
void update (int tp,int l,int r,int h,int v = 1,int tl = 0,int tr = nn - 1) {
      if (tl > r || tr < l) return ;

      if (l <= tl && tr <= r)
            upd(tp,v,h);
      else {
            push(v);
            int tm = (tl + tr) >> 1;
            update (tp,l,r,h,v + v,tl,tm);
            update (tp,l,r,h,v + v + 1,tm + 1,tr);
      }
}
void get(int finalHeight[],int v = 1,int tl = 0,int tr = nn - 1) {
      if (tl == tr)
            finalHeight[tl] = min(t[v].mx,t[v].mn);
      else {
            push(v);
            int tm = (tl + tr) >> 1;
            get(finalHeight,v + v,tl,tm);
            get(finalHeight,v + v + 1,tm + 1,tr);
      }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
      nn = n;

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

      get(finalHeight);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 62968 KB Output is correct
2 Correct 51 ms 63088 KB Output is correct
3 Correct 51 ms 63088 KB Output is correct
4 Correct 54 ms 63336 KB Output is correct
5 Correct 53 ms 63336 KB Output is correct
6 Correct 52 ms 63336 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 63336 KB Output is correct
2 Correct 241 ms 70976 KB Output is correct
3 Correct 244 ms 70976 KB Output is correct
4 Correct 616 ms 71756 KB Output is correct
5 Correct 374 ms 72236 KB Output is correct
6 Correct 373 ms 72236 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 72236 KB Output is correct
2 Correct 51 ms 72236 KB Output is correct
3 Correct 52 ms 72236 KB Output is correct
4 Correct 55 ms 72236 KB Output is correct
5 Correct 58 ms 72236 KB Output is correct
6 Correct 58 ms 72236 KB Output is correct
7 Correct 49 ms 72236 KB Output is correct
8 Correct 225 ms 72236 KB Output is correct
9 Correct 253 ms 72236 KB Output is correct
10 Correct 629 ms 72236 KB Output is correct
11 Correct 383 ms 72236 KB Output is correct
12 Correct 361 ms 72236 KB Output is correct
13 Correct 50 ms 72236 KB Output is correct
14 Correct 224 ms 72236 KB Output is correct
15 Correct 81 ms 72236 KB Output is correct
16 Correct 635 ms 72236 KB Output is correct
17 Correct 412 ms 72236 KB Output is correct
18 Correct 406 ms 72236 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 72236 KB Output is correct
2 Correct 51 ms 72236 KB Output is correct
3 Correct 56 ms 72236 KB Output is correct
4 Correct 71 ms 72236 KB Output is correct
5 Correct 55 ms 72236 KB Output is correct
6 Correct 55 ms 72236 KB Output is correct
7 Correct 56 ms 72236 KB Output is correct
8 Correct 247 ms 72236 KB Output is correct
9 Correct 277 ms 72236 KB Output is correct
10 Correct 717 ms 72236 KB Output is correct
11 Correct 437 ms 72236 KB Output is correct
12 Correct 387 ms 72236 KB Output is correct
13 Correct 55 ms 72236 KB Output is correct
14 Correct 226 ms 72236 KB Output is correct
15 Correct 81 ms 72236 KB Output is correct
16 Correct 682 ms 72236 KB Output is correct
17 Correct 403 ms 72236 KB Output is correct
18 Correct 376 ms 72236 KB Output is correct
19 Correct 782 ms 89148 KB Output is correct
20 Correct 766 ms 97000 KB Output is correct
21 Correct 803 ms 109864 KB Output is correct
22 Correct 772 ms 117860 KB Output is correct
23 Correct 866 ms 128392 KB Output is correct
24 Correct 782 ms 138780 KB Output is correct
25 Correct 829 ms 149320 KB Output is correct
26 Correct 784 ms 162156 KB Output is correct
27 Correct 844 ms 172640 KB Output is correct
28 Correct 778 ms 180684 KB Output is correct
29 Correct 777 ms 191144 KB Output is correct
30 Correct 851 ms 201476 KB Output is correct