oj.uz

Submission #171410

# Submission time Handle Problem Language Result Execution time Memory
171410 2019-12-28T15:43:47 Z gs18103 Wall (IOI14_wall) C++14
100 / 100
 965 ms 101480 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].fi >= val) 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].se <= val) 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:41:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  update1(node<<1, s, s+e>>1, l, r, val);
                      ~^~
wall.cpp:42: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:57:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  update2(node<<1, s, s+e>>1, l, r, val);
                      ~^~
wall.cpp:58: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:66:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(k <= (s+e>>1)) return cal(node<<1, s, s+e>>1, k);
           ~^~
wall.cpp:66:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(k <= (s+e>>1)) return cal(node<<1, s, s+e>>1, k);
                                           ~^~
wall.cpp:67: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 31968 KB Output is correct
3 Correct 31 ms 32004 KB Output is correct
4 Correct 37 ms 32504 KB Output is correct
5 Correct 35 ms 32376 KB Output is correct
6 Correct 35 ms 32376 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31992 KB Output is correct
2 Correct 200 ms 39960 KB Output is correct
3 Correct 211 ms 35832 KB Output is correct
4 Correct 580 ms 52088 KB Output is correct
5 Correct 366 ms 53112 KB Output is correct
6 Correct 359 ms 51576 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31992 KB Output is correct
2 Correct 31 ms 31992 KB Output is correct
3 Correct 31 ms 31992 KB Output is correct
4 Correct 40 ms 32376 KB Output is correct
5 Correct 35 ms 32408 KB Output is correct
6 Correct 35 ms 32436 KB Output is correct
7 Correct 29 ms 31992 KB Output is correct
8 Correct 205 ms 39772 KB Output is correct
9 Correct 213 ms 35832 KB Output is correct
10 Correct 582 ms 52076 KB Output is correct
11 Correct 367 ms 53108 KB Output is correct
12 Correct 361 ms 51576 KB Output is correct
13 Correct 29 ms 31992 KB Output is correct
14 Correct 206 ms 45692 KB Output is correct
15 Correct 69 ms 33656 KB Output is correct
16 Correct 840 ms 52348 KB Output is correct
17 Correct 397 ms 51704 KB Output is correct
18 Correct 399 ms 51840 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 31964 KB Output is correct
2 Correct 31 ms 31992 KB Output is correct
3 Correct 34 ms 31992 KB Output is correct
4 Correct 38 ms 32376 KB Output is correct
5 Correct 35 ms 32376 KB Output is correct
6 Correct 40 ms 32376 KB Output is correct
7 Correct 34 ms 31992 KB Output is correct
8 Correct 199 ms 39820 KB Output is correct
9 Correct 211 ms 35960 KB Output is correct
10 Correct 605 ms 52216 KB Output is correct
11 Correct 370 ms 53112 KB Output is correct
12 Correct 359 ms 51644 KB Output is correct
13 Correct 29 ms 31996 KB Output is correct
14 Correct 206 ms 45672 KB Output is correct
15 Correct 75 ms 33656 KB Output is correct
16 Correct 840 ms 52520 KB Output is correct
17 Correct 375 ms 51856 KB Output is correct
18 Correct 407 ms 51832 KB Output is correct
19 Correct 946 ms 101272 KB Output is correct
20 Correct 934 ms 98680 KB Output is correct
21 Correct 938 ms 101352 KB Output is correct
22 Correct 955 ms 98756 KB Output is correct
23 Correct 927 ms 98868 KB Output is correct
24 Correct 965 ms 98708 KB Output is correct
25 Correct 927 ms 98876 KB Output is correct
26 Correct 937 ms 101240 KB Output is correct
27 Correct 953 ms 101480 KB Output is correct
28 Correct 926 ms 98864 KB Output is correct
29 Correct 946 ms 98808 KB Output is correct
30 Correct 954 ms 98856 KB Output is correct