oj.uz

답안 #227981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
227981 2020-04-29T12:25:05 Z quocnguyen1012 벽 (IOI14_wall) C++14
61 / 100
 871 ms 36344 KB 
#ifndef LOCAL
#include "wall.h"
#endif // LOCAL

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array
#define lc id << 1
#define rc id << 1 | 1

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e5 + 5, mod = 1e9 + 7, inf = 1e9;;

int N;
int mx[4 * maxn],mn[4 * maxn];
int lzmin[4 * maxn], lzmax[4 * maxn];
int res[maxn];

void build(int id, int l, int r)
{
  lzmin[id] = inf;
  lzmax[id] = -inf;
  if(l == r) return;
  int mid = (l + r) / 2;
  build(lc, l, mid); build(rc, mid + 1, r);
}

void push(int id, int l, int r)
{
  mn[id] = min(mn[id], lzmin[id]);
  mn[id] = max(mn[id], lzmax[id]);
  mx[id] = max(mx[id], lzmax[id]);
  mx[id] = min(mx[id], lzmin[id]);
  if(l != r){
    lzmin[lc] = min(lzmin[lc], lzmin[id]);
    lzmin[rc] = min(lzmin[rc], lzmin[id]);
    lzmin[lc] = max(lzmin[lc], lzmax[id]);
    lzmin[rc] = max(lzmin[rc], lzmax[id]);


    lzmax[rc] = max(lzmax[rc], lzmax[id]);
    lzmax[lc] = max(lzmax[lc], lzmax[id]);
    lzmax[rc] = min(lzmax[rc], lzmin[id]);
    lzmax[lc] = min(lzmax[lc], lzmin[id]);

    lzmax[id] = -inf; lzmin[id] = inf;
  }
}

void modify(int L, int R, int val, int type, int id = 1, int l = 1, int r = N)
{
  push(id, l, r);
  if(R < l || r < L) return;
  if(L <= l && r <= R){
    if(type == 1){
      lzmin[id] = max(lzmin[id], val);
      lzmax[id] = max(lzmax[id], val);
    }
    else if(type == 2){
      lzmin[id] = min(lzmin[id], val);
      lzmax[id] = min(lzmax[id], val);
    }
    push(id, l, r);
    return;
  }
  int mid = (l + r) / 2;
  modify(L, R, val, type, lc, l, mid); modify(L, R, val, type, rc, mid + 1, r);
  mx[id] = max(mx[lc], mx[rc]);
  mn[id] = min(mn[lc], mn[rc]);
}

void comp(int id, int l, int r)
{
  push(id, l, r);
  if(l == r){
    assert(mx[id] == mn[id]);
    res[l] = mx[id];
    return;
  }
  int mid = (l + r) / 2;
  comp(lc, l, mid); comp(rc, mid + 1, r);
}

void buildWall(int _N, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
  N = _N;
  build(1, 1, N);
  for(int i = 0; i < k; ++i){
    modify(left[i] + 1, right[i] + 1, height[i], op[i]);
  }
  comp(1, 1, N);
  for(int i = 1; i <= N; ++i)
    finalHeight[i - 1] = res[i];
}
#ifdef LOCAL
signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int tc; cin >> N >> tc;
  build(1, 1, N);
  while(tc--){
    int le, ri, op, h;
    cin >> op >> le >> ri >> h;
    modify(le + 1, ri + 1, h, op);
  }
  comp(1, 1, N);
  for(int i = 1; i <= N; ++i)
    cout << res[i] << ' ';
}
#endif

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 13 ms 1152 KB Output is correct
5 Correct 16 ms 1128 KB Output is correct
6 Correct 12 ms 1152 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 178 ms 13948 KB Output is correct
3 Correct 317 ms 8640 KB Output is correct
4 Correct 847 ms 23036 KB Output is correct
5 Correct 506 ms 24112 KB Output is correct
6 Correct 512 ms 22392 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 13 ms 1152 KB Output is correct
5 Correct 12 ms 1152 KB Output is correct
6 Correct 13 ms 1280 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 187 ms 14032 KB Output is correct
9 Correct 295 ms 8696 KB Output is correct
10 Correct 866 ms 22860 KB Output is correct
11 Correct 515 ms 23928 KB Output is correct
12 Correct 513 ms 22392 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 177 ms 13944 KB Output is correct
15 Correct 50 ms 2680 KB Output is correct
16 Correct 869 ms 23160 KB Output is correct
17 Correct 508 ms 22776 KB Output is correct
18 Correct 502 ms 22520 KB Output is correct

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 13 ms 1152 KB Output is correct
5 Correct 12 ms 1152 KB Output is correct
6 Correct 12 ms 1152 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 182 ms 13944 KB Output is correct
9 Correct 310 ms 8568 KB Output is correct
10 Correct 860 ms 22872 KB Output is correct
11 Correct 529 ms 23928 KB Output is correct
12 Correct 504 ms 22396 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 178 ms 13944 KB Output is correct
15 Correct 52 ms 2680 KB Output is correct
16 Correct 871 ms 23208 KB Output is correct
17 Correct 508 ms 22580 KB Output is correct
18 Correct 502 ms 22648 KB Output is correct
19 Runtime error 218 ms 36344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -