oj.uz

답안 #50237

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
50237 2018-06-08T11:56:27 Z mirbek01 벽 (IOI14_wall) C++17
32 / 100
 849 ms 18972 KB 
#include "wall.h"

# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

struct st{
      int mx, mn, x, c, b, y;
      st(){
            mx = x = b = 0;
            mn = y = 1e5 + 1;
      }
}t[N * 4];

int n;

void push(int v, int tl, int tr){
      if(t[v].b){
            t[v].mx = max(t[v].mx, t[v].x);
            if(tl != tr){
                  t[v << 1].b = t[(v << 1) | 1].b = 1;
                  t[v << 1].x = max(t[v << 1].x, t[v].x);
                  t[(v << 1) | 1].x = max(t[(v << 1) | 1].x, t[v].x);
            }
            t[v].b = 0;
      }
      if(t[v].c){
            t[v].mn = min(t[v].mn, t[v].y);
            if(tl != tr){
                  t[v << 1].c = t[(v << 1) | 1].c = 1;
                  t[v << 1].y = min(t[v << 1].y, t[v].y);
                  t[(v << 1) | 1].y = min(t[(v << 1) | 1].y, t[v].y);
            }
            t[v].c = 0;
      }
}

void update(int l, int r, int x, int tp, int v = 1, int tl = 1, int tr = n){
      push(v, tl, tr);
      if(tl > r || l > tr) return ;
      if(l <= tl && tr <= r){
            if(tp == 1){
                  t[v].x = x;
                  t[v].b = 1;
            } else {
                  t[v].y = x;
                  t[v].c = 1;
            }
            push(v, tl, tr);
            return ;
      }
      int tm = (tl + tr) >> 1;
      update(l, r, x, tp, v << 1, tl, tm);
      update(l, r, x, tp, (v << 1) | 1, tm + 1, tr);
}

int get(int pos, int v = 1, int tl = 1, int tr = n){
      push(v, tl, tr);
      if(tl == tr){
            return min(t[v].mn, t[v].mx);
      }
      int tm = (tl + tr) >> 1;
      if(pos <= tm)
            return get(pos, v << 1, tl, tm);
      return get(pos, (v << 1) | 1, tm + 1, tr);
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
      n = N;

      if(n <= 10000 && k <= 5000){
            for(int i = 0; i < k; i ++){
                  for(int j = left[i]; j <= right[i]; j ++){
                        if(op[i] == 1){
                              finalHeight[j] = max(finalHeight[j], height[i]);
                        } else {
                              finalHeight[j] = min(finalHeight[j], height[i]);
                        }
                  }
            }
      } else {
            for(int i = 0; i < k; i ++){
                  update(left[i] + 1, right[i] + 1, height[i], op[i]);
            }
            for(int i = 0; i < n; i ++){
                  finalHeight[i] = get(i + 1);
            }
      }
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 11 ms 9832 KB Output is correct
3 Correct 10 ms 9832 KB Output is correct
4 Correct 34 ms 9952 KB Output is correct
5 Correct 33 ms 9952 KB Output is correct
6 Correct 33 ms 9968 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 9968 KB Output is correct
2 Correct 186 ms 17696 KB Output is correct
3 Correct 278 ms 17696 KB Output is correct
4 Correct 754 ms 18368 KB Output is correct
5 Correct 354 ms 18948 KB Output is correct
6 Correct 348 ms 18948 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 18948 KB Output is correct
2 Correct 11 ms 18948 KB Output is correct
3 Correct 10 ms 18948 KB Output is correct
4 Correct 38 ms 18948 KB Output is correct
5 Correct 38 ms 18948 KB Output is correct
6 Correct 34 ms 18948 KB Output is correct
7 Correct 10 ms 18948 KB Output is correct
8 Correct 196 ms 18948 KB Output is correct
9 Correct 262 ms 18948 KB Output is correct
10 Correct 763 ms 18948 KB Output is correct
11 Correct 346 ms 18972 KB Output is correct
12 Correct 384 ms 18972 KB Output is correct
13 Correct 9 ms 18972 KB Output is correct
14 Incorrect 206 ms 18972 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 18972 KB Output is correct
2 Correct 13 ms 18972 KB Output is correct
3 Correct 10 ms 18972 KB Output is correct
4 Correct 37 ms 18972 KB Output is correct
5 Correct 32 ms 18972 KB Output is correct
6 Correct 33 ms 18972 KB Output is correct
7 Correct 9 ms 18972 KB Output is correct
8 Correct 202 ms 18972 KB Output is correct
9 Correct 271 ms 18972 KB Output is correct
10 Correct 849 ms 18972 KB Output is correct
11 Correct 353 ms 18972 KB Output is correct
12 Correct 350 ms 18972 KB Output is correct
13 Correct 10 ms 18972 KB Output is correct
14 Incorrect 204 ms 18972 KB Output isn't correct
15 Halted 0 ms 0 KB -