oj.uz

Submission #23228

# Submission time Handle Problem Language Result Execution time Memory
23228 2017-05-05T10:27:39 Z RockyB Wall (IOI14_wall) C++14
61 / 100
 713 ms 68440 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 = 1e6 + 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 52800 KB Output is correct
2 Correct 0 ms 52936 KB Output is correct
3 Correct 0 ms 52800 KB Output is correct
4 Correct 3 ms 52936 KB Output is correct
5 Correct 3 ms 52936 KB Output is correct
6 Correct 3 ms 52936 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 52800 KB Output is correct
2 Correct 169 ms 60624 KB Output is correct
3 Correct 186 ms 56196 KB Output is correct
4 Correct 526 ms 61016 KB Output is correct
5 Correct 309 ms 61016 KB Output is correct
6 Correct 349 ms 61016 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 52800 KB Output is correct
2 Correct 0 ms 52936 KB Output is correct
3 Correct 0 ms 52800 KB Output is correct
4 Correct 3 ms 52936 KB Output is correct
5 Correct 3 ms 52936 KB Output is correct
6 Correct 3 ms 52936 KB Output is correct
7 Correct 0 ms 52800 KB Output is correct
8 Correct 166 ms 60624 KB Output is correct
9 Correct 179 ms 56196 KB Output is correct
10 Correct 539 ms 61016 KB Output is correct
11 Correct 313 ms 61016 KB Output is correct
12 Correct 326 ms 61016 KB Output is correct
13 Correct 0 ms 52800 KB Output is correct
14 Correct 156 ms 60624 KB Output is correct
15 Correct 33 ms 53428 KB Output is correct
16 Correct 543 ms 61016 KB Output is correct
17 Correct 329 ms 61016 KB Output is correct
18 Correct 306 ms 61016 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 52800 KB Output is correct
2 Correct 0 ms 52936 KB Output is correct
3 Correct 0 ms 52800 KB Output is correct
4 Correct 3 ms 52936 KB Output is correct
5 Correct 3 ms 52936 KB Output is correct
6 Correct 3 ms 52936 KB Output is correct
7 Correct 0 ms 52800 KB Output is correct
8 Correct 179 ms 60624 KB Output is correct
9 Correct 186 ms 56196 KB Output is correct
10 Correct 533 ms 61016 KB Output is correct
11 Correct 319 ms 61016 KB Output is correct
12 Correct 353 ms 61016 KB Output is correct
13 Correct 0 ms 52800 KB Output is correct
14 Correct 163 ms 60624 KB Output is correct
15 Correct 26 ms 53428 KB Output is correct
16 Correct 526 ms 61016 KB Output is correct
17 Correct 316 ms 61016 KB Output is correct
18 Correct 353 ms 61016 KB Output is correct
19 Incorrect 713 ms 68440 KB Output isn't correct
20 Halted 0 ms 0 KB -