oj.uz

Submission #260928

# Submission time Handle Problem Language Result Execution time Memory
260928 2020-08-11T08:10:00 Z my99n Wall (IOI14_wall) C++14
0 / 100
 1 ms 256 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000100;

struct A {
  int mn, mx;
} seg[MAXN];

int* ans, N;

void tag (int now, int mn, int mx) {
  cerr << "tag" << now << ' ' << mn << ' ' << mx << endl;
  seg[now].mn = min(mx, max(mn, seg[now].mn));
  seg[now].mx = max(mn, min(mx, seg[now].mx));
}

void push (int now, int l, int r) {
  if (l == r) return;
  tag(now*2, seg[now].mn, seg[now].mx);
  tag(now*2+1, seg[now].mn, seg[now].mx);
  seg[now].mn = 0;
  seg[now].mx = 1e9;
}

void build (int now = 1, int l = 1, int r = N) {
  seg[now].mn = 0;
  seg[now].mx = 1e9;
  if (l == r) return;
  int mid = (l+r)/2;
  build(now*2, l, mid);
  build(now*2+1, mid+1, r);
}

void update (int a, int b, int mn, int mx, int now = 1, int l = 1, int r = N) {
  if (r < a or l > b) return;
  if (a <= l and r <= b) return tag(now, mn, mx);
  push(now, l, r);
  int mid = (l+r)/2;
  update(a, b, mn, mx, now*2, l, mid);
  update(a, b, mn, mx, now*2+1, mid+1, r);
}

void dfs (int now = 1, int l = 1, int r = N) {
  if (l == r) {
    ans[l] = min(seg[now].mn, seg[now].mx);
    return;
  }
  push(now, l, r);
  int mid = (l+r)/2;
  dfs(now*2, l, mid);
  dfs(now*2+1, mid+1, r);
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int finalHeight[]){
	ans = finalHeight;
	N = n;
	build();
	for(int i = 0; i < k; i++) {
		if(op[i] == 1) update(l[i], r[i], h[i], 1e9);
		else if(op[i] == 2) update(l[i], r[i], 0, h[i]);
	}
	dfs();
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -