Submission #171405

#	Time	Username	Problem	Language	Result	Execution time	Memory
171405		gs18103	Wall (IOI14_wall)	C++14	8 / 100	3051 ms	45732 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define report(x, l, s) stype[x] = s, location[x] = l, chk[x] = true

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 2020202;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;

pii tree[4*MAX];
int lazy[4*MAX];

void update_lazy(int node, int s, int e) {
	if(lazy[node] == -1) return;
	tree[node].fi = tree[node].se = lazy[node];
	if(s != e) {
		lazy[node<<1] = lazy[node<<1|1] = lazy[node];
	}
	lazy[node] = -1;
}

void update1(int node, int s, int e, int l, int r, int val) {
	update_lazy(node, s, e);
	if(s > r || e < l) return;
	if(s >= l && e <= r && tree[node].se <= val) {
		lazy[node] = val;
		update_lazy(node, s, e);
		return;
	}
	if(s == e) return;
	update1(node<<1, s, s+e>>1, l, r, val);
	update1(node<<1|1, (s+e>>1)+1, e, l, r, val);
	tree[node].fi = min(tree[node<<1].fi, tree[node<<1|1].fi);
	tree[node].se = max(tree[node<<1].se, tree[node<<1|1].se);
}

void update2(int node, int s, int e, int l, int r, int val) {
	update_lazy(node, s, e);
	if(s > r || e < l) return;
	if(s >= l && e <= r && tree[node].fi >= val) {
		lazy[node] = val;
		update_lazy(node, s, e);
		return;
	}
	if(s == e) return;
	update2(node<<1, s, s+e>>1, l, r, val);
	update2(node<<1|1, (s+e>>1)+1, e, l, r, val);
	tree[node].fi = min(tree[node<<1].fi, tree[node<<1|1].fi);
	tree[node].se = max(tree[node<<1].se, tree[node<<1|1].se);
}

int cal(int node, int s, int e, int k) {
	update_lazy(node, s, e);
	if(s == e) return tree[node].fi;
	if(k <= (s+e>>1)) return cal(node<<1, s, s+e>>1, k);
	else return cal(node<<1|1, (s+e>>1)+1, e, k);
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
	for(int i = 0; i < 4 * MAX; i++) {
		lazy[i] = -1;
	}
	for(int i = 0; i < k; i++) {
		if(op[i] == 1) update1(1, 0, n-1, l[i], r[i], h[i]);
		else update2(1, 0, n-1, l[i], r[i], h[i]);
	}
	for(int i = 0; i < n; i++) {
		ans[i] = cal(1, 0, n-1, i);
	}
}

Compilation message (stderr)

wall.cpp: In function 'void update1(int, int, int, int, int, int)':
wall.cpp:40:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  update1(node<<1, s, s+e>>1, l, r, val);
                      ~^~
wall.cpp:41:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  update1(node<<1|1, (s+e>>1)+1, e, l, r, val);
                      ~^~
wall.cpp: In function 'void update2(int, int, int, int, int, int)':
wall.cpp:55:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  update2(node<<1, s, s+e>>1, l, r, val);
                      ~^~
wall.cpp:56:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  update2(node<<1|1, (s+e>>1)+1, e, l, r, val);
                      ~^~
wall.cpp: In function 'int cal(int, int, int, int)':
wall.cpp:64:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(k <= (s+e>>1)) return cal(node<<1, s, s+e>>1, k);
           ~^~
wall.cpp:64:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(k <= (s+e>>1)) return cal(node<<1, s, s+e>>1, k);
                                           ~^~
wall.cpp:65:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else return cal(node<<1|1, (s+e>>1)+1, e, k);
                              ~^~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39