oj.uz

Submission #305082

# Submission time Handle Problem Language Result Execution time Memory
305082 2020-09-22T14:29:41 Z vipghn2003 Wall (IOI14_wall) C++14
100 / 100
 1263 ms 99960 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 0 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1056 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 181 ms 8240 KB Output is correct
3 Correct 296 ms 4856 KB Output is correct
4 Correct 895 ms 13432 KB Output is correct
5 Correct 497 ms 13816 KB Output is correct
6 Correct 482 ms 13816 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 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 180 ms 8232 KB Output is correct
9 Correct 286 ms 4856 KB Output is correct
10 Correct 908 ms 13432 KB Output is correct
11 Correct 504 ms 13816 KB Output is correct
12 Correct 490 ms 13944 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 180 ms 8184 KB Output is correct
15 Correct 47 ms 2040 KB Output is correct
16 Correct 895 ms 13560 KB Output is correct
17 Correct 518 ms 13560 KB Output is correct
18 Correct 497 ms 13560 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 180 ms 8184 KB Output is correct
9 Correct 298 ms 4856 KB Output is correct
10 Correct 900 ms 13304 KB Output is correct
11 Correct 503 ms 13820 KB Output is correct
12 Correct 491 ms 13944 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 184 ms 8184 KB Output is correct
15 Correct 48 ms 2040 KB Output is correct
16 Correct 905 ms 13688 KB Output is correct
17 Correct 487 ms 13560 KB Output is correct
18 Correct 508 ms 13560 KB Output is correct
19 Correct 1257 ms 99960 KB Output is correct
20 Correct 1237 ms 97528 KB Output is correct
21 Correct 1245 ms 99832 KB Output is correct
22 Correct 1254 ms 97400 KB Output is correct
23 Correct 1234 ms 97400 KB Output is correct
24 Correct 1248 ms 97528 KB Output is correct
25 Correct 1252 ms 97400 KB Output is correct
26 Correct 1256 ms 99960 KB Output is correct
27 Correct 1255 ms 99960 KB Output is correct
28 Correct 1245 ms 97404 KB Output is correct
29 Correct 1263 ms 97400 KB Output is correct
30 Correct 1241 ms 97624 KB Output is correct