oj.uz

Submission #1031063

# Submission time Handle Problem Language Result Execution time Memory
1031063 2024-07-22T14:09:45 Z tolbi Wall (IOI14_wall) C++17
100 / 100
 1048 ms 103348 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1e9+7;
#define tol(bi) (1LL<<((int)(bi)))
void _upd(array<int,4> &old, array<int,3> upd){
	if (upd[1]==1){
		if (old[0]<=upd[0]){
			old[0]=min(old[2],max(old[0],upd[0]));
			old[1]=upd[2];
		}
	}
	else {
		if (old[2]>=upd[0]){
			old[2]=max(old[0],min(old[2],upd[0]));
			old[3]=upd[2];
		}
	}
}
constexpr int MAXN = 2000000;
array<int,2> segtree[MAXN*4];
array<int,2> lazy[MAXN*4];
void upd(array<int,2> &old, array<int,2> &u){
	old[1]=max(old[1],u[0]);
	old[0]=min(old[0],u[1]);
	old[0]=max(old[0],u[0]);
	old[1]=min(old[1],u[1]);
}
struct SegTree{
	int sz;
	SegTree(int n){
		sz=tol(ceil(log2(n)+1))-1;
		fill(segtree,segtree+sz,array<int,2>{-1,MOD});
		fill(lazy,lazy+sz,array<int,2>{-1,MOD});
	}
	void dallan(int node){
		upd(segtree[node],lazy[node]);
		if (node*2+1<sz){
			upd(lazy[node*2+1],lazy[node]);
			upd(lazy[node*2+2],lazy[node]);
		}
		lazy[node]={-1,MOD};
	}
	void update(int tl, int tr, array<int,2> val, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = sz/2;
		dallan(node);
		if (l>=tl && r<=tr){
			return lazy[node]=val, dallan(node);
		}
		if (l>tr || r<tl) return;
		int mid = l+(r-l)/2;
		if (tl<=mid) update(tl, tr, val, l, mid, node*2+1);
		if (mid<tr) update(tl, tr, val, mid+1, r, node*2+2);
	}
	int query(int x){
		int l = 0, r = sz/2;
		int node = 0;
		dallan(node);
		while (l<r){
			int mid = l+(r-l)/2;
			if (mid>=x){
				r=mid,node=node*2+1;
			}
			else {
				l=mid+1,node=node*2+2;
			}
			dallan(node);
		}
		return segtree[node][0];
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegTree segtree(n);
	for (int i = 0; i < k; i++){
		if (op[i]==1){
			segtree.update(left[i],right[i],{height[i],MOD});
		}
		else {
			segtree.update(left[i],right[i],{-1,height[i]});
		}
	}
	for (int i = 0; i < n; ++i)
	{
		finalHeight[i]=max(0,segtree.query(i));
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1168 KB Output is correct
5 Correct 6 ms 2908 KB Output is correct
6 Correct 6 ms 1112 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 84 ms 11384 KB Output is correct
3 Correct 152 ms 8620 KB Output is correct
4 Correct 446 ms 23380 KB Output is correct
5 Correct 240 ms 24496 KB Output is correct
6 Correct 255 ms 22752 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1112 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 7 ms 1212 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 84 ms 15488 KB Output is correct
9 Correct 158 ms 9812 KB Output is correct
10 Correct 475 ms 22500 KB Output is correct
11 Correct 254 ms 23632 KB Output is correct
12 Correct 230 ms 21840 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 84 ms 14028 KB Output is correct
15 Correct 25 ms 2644 KB Output is correct
16 Correct 452 ms 22612 KB Output is correct
17 Correct 247 ms 22100 KB Output is correct
18 Correct 227 ms 23132 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 83 ms 13472 KB Output is correct
9 Correct 151 ms 9300 KB Output is correct
10 Correct 461 ms 22500 KB Output is correct
11 Correct 227 ms 23632 KB Output is correct
12 Correct 222 ms 22000 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 98 ms 14040 KB Output is correct
15 Correct 27 ms 2652 KB Output is correct
16 Correct 471 ms 22612 KB Output is correct
17 Correct 238 ms 22244 KB Output is correct
18 Correct 257 ms 22980 KB Output is correct
19 Correct 1048 ms 103332 KB Output is correct
20 Correct 978 ms 100688 KB Output is correct
21 Correct 991 ms 103248 KB Output is correct
22 Correct 1036 ms 100860 KB Output is correct
23 Correct 973 ms 100872 KB Output is correct
24 Correct 984 ms 100688 KB Output is correct
25 Correct 976 ms 100688 KB Output is correct
26 Correct 982 ms 103348 KB Output is correct
27 Correct 1014 ms 103252 KB Output is correct
28 Correct 981 ms 100616 KB Output is correct
29 Correct 976 ms 100692 KB Output is correct
30 Correct 983 ms 100872 KB Output is correct