oj.uz

Submission #305069

# Submission time Handle Problem Language Result Execution time Memory
305069 2020-09-22T14:04:21 Z vipghn2003 Wall (IOI14_wall) C++14
100 / 100
 1438 ms 110456 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 = 2e6 + 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] = min(mx[id], lzmin[id]);
  mx[id] = max(mx[id], lzmax[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] = min(lzmax[rc], lzmin[id]);
    lzmax[lc] = min(lzmax[lc], lzmin[id]);
    lzmax[rc] = max(lzmax[rc], lzmax[id]);
    lzmax[lc] = max(lzmax[lc], lzmax[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] = min(mx[lc], mx[rc]);
  mn[id] = max(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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 10 ms 1152 KB Output is correct
5 Correct 9 ms 1152 KB Output is correct
6 Correct 9 ms 1152 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 196 ms 14076 KB Output is correct
3 Correct 334 ms 8696 KB Output is correct
4 Correct 1030 ms 22904 KB Output is correct
5 Correct 574 ms 23976 KB Output is correct
6 Correct 576 ms 22416 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 10 ms 1152 KB Output is correct
5 Correct 9 ms 1152 KB Output is correct
6 Correct 10 ms 1152 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 187 ms 13944 KB Output is correct
9 Correct 335 ms 8572 KB Output is correct
10 Correct 1036 ms 23032 KB Output is correct
11 Correct 572 ms 23928 KB Output is correct
12 Correct 567 ms 22648 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 193 ms 14020 KB Output is correct
15 Correct 54 ms 2680 KB Output is correct
16 Correct 1029 ms 23112 KB Output is correct
17 Correct 562 ms 22648 KB Output is correct
18 Correct 572 ms 22648 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 10 ms 1152 KB Output is correct
5 Correct 9 ms 1152 KB Output is correct
6 Correct 9 ms 1152 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 181 ms 13944 KB Output is correct
9 Correct 336 ms 8648 KB Output is correct
10 Correct 1022 ms 22968 KB Output is correct
11 Correct 590 ms 23928 KB Output is correct
12 Correct 563 ms 22396 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 184 ms 14072 KB Output is correct
15 Correct 53 ms 2680 KB Output is correct
16 Correct 1045 ms 23288 KB Output is correct
17 Correct 561 ms 22520 KB Output is correct
18 Correct 563 ms 22648 KB Output is correct
19 Correct 1436 ms 110456 KB Output is correct
20 Correct 1418 ms 107724 KB Output is correct
21 Correct 1427 ms 110376 KB Output is correct
22 Correct 1419 ms 108024 KB Output is correct
23 Correct 1417 ms 108024 KB Output is correct
24 Correct 1428 ms 107896 KB Output is correct
25 Correct 1421 ms 107756 KB Output is correct
26 Correct 1426 ms 110456 KB Output is correct
27 Correct 1438 ms 110368 KB Output is correct
28 Correct 1424 ms 107768 KB Output is correct
29 Correct 1435 ms 108024 KB Output is correct
30 Correct 1424 ms 108024 KB Output is correct