oj.uz

Submission #171405

# Submission time Handle Problem Language Result Execution time Memory
171405 2019-12-28T15:39:06 Z gs18103 Wall (IOI14_wall) C++14
8 / 100
 3000 ms 45732 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31992 KB Output is correct
2 Correct 32 ms 32120 KB Output is correct
3 Correct 34 ms 31992 KB Output is correct
4 Correct 154 ms 32504 KB Output is correct
5 Correct 51 ms 32504 KB Output is correct
6 Correct 52 ms 32504 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 31992 KB Output is correct
2 Correct 217 ms 45732 KB Output is correct
3 Execution timed out 3040 ms 39604 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31992 KB Output is correct
2 Correct 32 ms 32156 KB Output is correct
3 Correct 32 ms 31992 KB Output is correct
4 Correct 154 ms 32504 KB Output is correct
5 Correct 51 ms 32424 KB Output is correct
6 Correct 52 ms 32508 KB Output is correct
7 Correct 29 ms 31996 KB Output is correct
8 Correct 204 ms 45560 KB Output is correct
9 Execution timed out 3051 ms 39544 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31992 KB Output is correct
2 Correct 31 ms 32120 KB Output is correct
3 Correct 32 ms 32080 KB Output is correct
4 Correct 154 ms 32452 KB Output is correct
5 Correct 50 ms 32504 KB Output is correct
6 Correct 52 ms 32504 KB Output is correct
7 Correct 29 ms 31992 KB Output is correct
8 Correct 203 ms 45688 KB Output is correct
9 Execution timed out 3045 ms 39672 KB Time limit exceeded
10 Halted 0 ms 0 KB -