oj.uz

Submission #52767

# Submission time Handle Problem Language Result Execution time Memory
52767 2018-06-26T17:17:55 Z szawinis Wall (IOI14_wall) C++17
100 / 100
 1115 ms 355704 KB 
#include <bits/stdc++.h>
using namespace std;
#define fori(i, a, b) for(int i = (int) a; i <= (int) b; ++i)
#define rofi(i, b, a) for(int i = (int) b; i >= (int) a; --i)
#define foreach(tt, a) for(auto &tt: a)
#define all(a) begin(a), end(a)
#define csz(a) (int) a.size()
#define pb push_back
#define epb emplace_back
#define mp make_pair
#define load(a, v) fill(begin(a), end(a), v)
#define load_mem(a, v) memset(a, v, sizeof(a));
#define iostream_optimize() ios::sync_with_stdio(false); cin.tie(0);
using ll = long long;
const ll MOD = 1e9+7, LINF = 1e16+1;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const ll P1 = 31, P2 = 37, M1 = 1e9+7, M2 = 1e9+9;
/* <<<<<<<<<<<<<<<<<<<<<<<<<<<< END TEMPLATE >>>>>>>>>>>>>>>>>>>>>>>>>>> */
#include "wall.h"
const int N = 1 << 21;

int mx[N << 1], mn[N << 1];

void puttag(int i, int v, int tp) {
  if(tp == 1) {
    mx[i] = max(v, mx[i]);
    mn[i] = max(v, mn[i]);
  } else {
    mx[i] = min(v, mx[i]);
    mn[i] = min(v, mn[i]);
  }
}

void apply(int i) {
  if(i >= N) return;
  puttag(i << 1, mx[i], 1);
  puttag(i << 1, mn[i], 2);
  puttag(i << 1 | 1, mx[i], 1);
  puttag(i << 1 | 1, mn[i], 2);
  mx[i] = 0, mn[i] = INF;
}

void update(int tl, int tr, int v, int tp, int i, int l, int r) {
  apply(i);
  if(l > tr || r < tl) return;
  if(tl <= l && r <= tr) {
    puttag(i, v, tp);
    return;
  }
  int mid = l+r >> 1;
  update(tl, tr, v, tp, i << 1, l, mid);
  update(tl, tr, v, tp, i << 1 | 1, mid+1, r);
  // cout << i << ' ' << l << ' ' << r << ' ' << mn[i] << ' ' << mx[i] << endl;
}

void propogate(int i, int l, int r) {
  apply(i);
  if(l == r) return;
  int mid = l+r >> 1;
  propogate(i << 1, l, mid);
  propogate(i << 1 | 1, mid+1, r);
}

void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[]) {
  load(mn, INF);
  fori(i, 0, q-1) update(left[i], right[i], height[i], op[i], 1, 0, N-1);
  propogate(1, 0, N-1);
  fori(i, 0, n-1) finalHeight[i] = mx[N+i];
  // fori(i, 0, 2*N-1) cout << mn[i] << ' ' << mx[i] << endl;
}

Compilation message

wall.cpp: In function 'void update(int, int, int, int, int, int, int)':
wall.cpp:52:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l+r >> 1;
             ~^~
wall.cpp: In function 'void propogate(int, int, int)':
wall.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l+r >> 1;
             ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 33152 KB Output is correct
2 Correct 60 ms 33252 KB Output is correct
3 Correct 60 ms 33328 KB Output is correct
4 Correct 79 ms 33620 KB Output is correct
5 Correct 64 ms 33708 KB Output is correct
6 Correct 66 ms 33808 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 33808 KB Output is correct
2 Correct 562 ms 41580 KB Output is correct
3 Correct 301 ms 41580 KB Output is correct
4 Correct 759 ms 51780 KB Output is correct
5 Correct 578 ms 62544 KB Output is correct
6 Correct 545 ms 71264 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 71264 KB Output is correct
2 Correct 62 ms 71264 KB Output is correct
3 Correct 68 ms 71264 KB Output is correct
4 Correct 66 ms 71264 KB Output is correct
5 Correct 65 ms 71264 KB Output is correct
6 Correct 67 ms 71264 KB Output is correct
7 Correct 56 ms 71264 KB Output is correct
8 Correct 593 ms 76088 KB Output is correct
9 Correct 343 ms 76088 KB Output is correct
10 Correct 750 ms 90092 KB Output is correct
11 Correct 524 ms 100912 KB Output is correct
12 Correct 530 ms 109484 KB Output is correct
13 Correct 57 ms 109484 KB Output is correct
14 Correct 657 ms 114180 KB Output is correct
15 Correct 94 ms 114180 KB Output is correct
16 Correct 861 ms 125232 KB Output is correct
17 Correct 668 ms 134320 KB Output is correct
18 Correct 489 ms 143428 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 143428 KB Output is correct
2 Correct 71 ms 143428 KB Output is correct
3 Correct 65 ms 143428 KB Output is correct
4 Correct 61 ms 143428 KB Output is correct
5 Correct 72 ms 143428 KB Output is correct
6 Correct 58 ms 143428 KB Output is correct
7 Correct 64 ms 143428 KB Output is correct
8 Correct 585 ms 148732 KB Output is correct
9 Correct 341 ms 148732 KB Output is correct
10 Correct 878 ms 162668 KB Output is correct
11 Correct 641 ms 173312 KB Output is correct
12 Correct 467 ms 182072 KB Output is correct
13 Correct 54 ms 182072 KB Output is correct
14 Correct 600 ms 186512 KB Output is correct
15 Correct 97 ms 186512 KB Output is correct
16 Correct 775 ms 197552 KB Output is correct
17 Correct 469 ms 206600 KB Output is correct
18 Correct 540 ms 215664 KB Output is correct
19 Correct 1115 ms 243028 KB Output is correct
20 Correct 847 ms 251168 KB Output is correct
21 Correct 866 ms 264096 KB Output is correct
22 Correct 929 ms 272088 KB Output is correct
23 Correct 957 ms 282532 KB Output is correct
24 Correct 873 ms 293120 KB Output is correct
25 Correct 901 ms 303436 KB Output is correct
26 Correct 848 ms 316456 KB Output is correct
27 Correct 995 ms 326808 KB Output is correct
28 Correct 839 ms 334752 KB Output is correct
29 Correct 840 ms 345280 KB Output is correct
30 Correct 839 ms 355704 KB Output is correct