oj.uz

Submission #23229

# Submission time Handle Problem Language Result Execution time Memory
23229 2017-05-05T10:28:23 Z RockyB Wall (IOI14_wall) C++14
100 / 100
 729 ms 119220 KB 
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

#include "wall.h"

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)

#define dbg(x) cerr << (#x) << " --> " << (x) << nl;
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

#define Toktama ""

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree < pair <int, int>, null_type, less < pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 2e6 + 7, inf = 1e9 + 7, mod = 1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

int n, k;
int type[N], l[N], r[N], x[N], ans[N];

int d[N << 2], u[N << 2];

void build(int v, int tl, int tr) {
  d[v] = inf, u[v] = 0;
  if (tl == tr) return;
  int tm = tl + tr >> 1;
  build(v + v, tl, tm);
  build(v + v + 1, tm + 1, tr);
}
void push(int v) {
  d[v + v] = min(d[v + v], d[v]);
  d[v + v] = max(d[v + v], u[v]);
  d[v + v + 1] = min(d[v + v + 1], d[v]);
  d[v + v + 1] = max(d[v + v + 1], u[v]);

  u[v + v] = max(u[v + v], u[v]);
  u[v + v] = min(u[v + v], d[v]);
  u[v + v + 1] = max(u[v + v + 1], u[v]);
  u[v + v + 1] = min(u[v + v + 1], d[v]);

  d[v] = inf, u[v] = 0;
}
void upd(int l, int r, int x, int type, int v, int tl, int tr) {
  if (l <= tl && tr <= r) {
    if (type == 1) {
      d[v] = max(d[v], x);
      u[v] = max(u[v], x);
    }
    else {
      u[v] = min(u[v], x);
      d[v] = min(d[v], x);
    }
    return;
  }
  if (tl > r || tr < l) return;
  int tm = tl + tr >> 1;
  push(v);
  upd(l, r, x, type, v + v, tl, tm);
  upd(l, r, x, type, v + v + 1, tm + 1, tr);
}
void out(int *a, int v, int tl, int tr) {
  if (tl == tr) {
    a[tl] = min(d[v], u[v]);
    return;
  }
  int tm = tl + tr >> 1;
  push(v);
  out(a, v + v, tl, tm);
  out(a, v + v + 1, tm + 1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  build(1, 0, n - 1);
  rep(i, 0, k - 1)
    upd(left[i], right[i], height[i], op[i], 1, 0, n - 1);
  out(finalHeight, 1, 0, n - 1);
}
/*
int main() {
  #ifndef Toktama
    freopen (Toktama".in", "r", stdin);
    freopen (Toktama".out", "w", stdout);
  #endif
  //freopen (".in", "r", stdin);
  //freopen ("gen.in", "r", stdin);
  //freopen ("a.out", "w", stdout);
  scanf ("%d%d", &n, &k);
  rep(i, 0, k - 1)
    scanf ("%d%d%d%d", &type[i], &l[i], &r[i], &x[i]);
  buildWall(n, k, type, l, r, x, ans);
  rep(i, 0, n - 1)
    printf ("%d ", ans[i]);

  {
    cout << nl;
    //bye(1, 0, n - 1);
  }

  ioi
}
*/

Compilation message

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:51:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int tm = tl + tr >> 1;
               ^
wall.cpp: In function 'void upd(int, int, int, int, int, int, int)':
wall.cpp:81:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int tm = tl + tr >> 1;
               ^
wall.cpp: In function 'void out(int*, int, int, int)':
wall.cpp:91:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int tm = tl + tr >> 1;
               ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 103580 KB Output is correct
2 Correct 0 ms 103716 KB Output is correct
3 Correct 0 ms 103580 KB Output is correct
4 Correct 6 ms 103716 KB Output is correct
5 Correct 3 ms 103716 KB Output is correct
6 Correct 3 ms 103716 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 103580 KB Output is correct
2 Correct 169 ms 111404 KB Output is correct
3 Correct 186 ms 106976 KB Output is correct
4 Correct 523 ms 111796 KB Output is correct
5 Correct 329 ms 111796 KB Output is correct
6 Correct 309 ms 111796 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 103580 KB Output is correct
2 Correct 0 ms 103716 KB Output is correct
3 Correct 0 ms 103580 KB Output is correct
4 Correct 3 ms 103716 KB Output is correct
5 Correct 3 ms 103716 KB Output is correct
6 Correct 3 ms 103716 KB Output is correct
7 Correct 0 ms 103580 KB Output is correct
8 Correct 189 ms 111404 KB Output is correct
9 Correct 193 ms 106976 KB Output is correct
10 Correct 529 ms 111796 KB Output is correct
11 Correct 306 ms 111796 KB Output is correct
12 Correct 303 ms 111796 KB Output is correct
13 Correct 0 ms 103580 KB Output is correct
14 Correct 163 ms 111404 KB Output is correct
15 Correct 29 ms 104208 KB Output is correct
16 Correct 536 ms 111796 KB Output is correct
17 Correct 299 ms 111796 KB Output is correct
18 Correct 389 ms 111796 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 103580 KB Output is correct
2 Correct 0 ms 103716 KB Output is correct
3 Correct 0 ms 103580 KB Output is correct
4 Correct 3 ms 103716 KB Output is correct
5 Correct 3 ms 103716 KB Output is correct
6 Correct 3 ms 103716 KB Output is correct
7 Correct 0 ms 103580 KB Output is correct
8 Correct 166 ms 111404 KB Output is correct
9 Correct 179 ms 106976 KB Output is correct
10 Correct 516 ms 111796 KB Output is correct
11 Correct 306 ms 111796 KB Output is correct
12 Correct 296 ms 111796 KB Output is correct
13 Correct 0 ms 103580 KB Output is correct
14 Correct 166 ms 111404 KB Output is correct
15 Correct 29 ms 104208 KB Output is correct
16 Correct 516 ms 111796 KB Output is correct
17 Correct 313 ms 111796 KB Output is correct
18 Correct 329 ms 111796 KB Output is correct
19 Correct 726 ms 119220 KB Output is correct
20 Correct 669 ms 119220 KB Output is correct
21 Correct 713 ms 119220 KB Output is correct
22 Correct 713 ms 119220 KB Output is correct
23 Correct 713 ms 119220 KB Output is correct
24 Correct 713 ms 119220 KB Output is correct
25 Correct 729 ms 119220 KB Output is correct
26 Correct 706 ms 119220 KB Output is correct
27 Correct 696 ms 119220 KB Output is correct
28 Correct 729 ms 119220 KB Output is correct
29 Correct 703 ms 119220 KB Output is correct
30 Correct 686 ms 119220 KB Output is correct