oj.uz

Submission #779815

# Submission time Handle Problem Language Result Execution time Memory
779815 2023-07-11T23:37:27 Z YassirSalama Wall (IOI14_wall) C++14
100 / 100
 618 ms 69524 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
// #define int long long
const int MAXN=2e6;
const int INF=1e9+7;
struct Node{
	int mn;
	int mx;
};
Node tree[4*MAXN];
void build(int node,int l,int r){
	tree[node].mn=INF;
	tree[node].mx=-INF;
	if(l==r) return;
	int mid=(l+r)/2;
	build(node<<1,l,mid);
	build(node<<1|1,mid+1,r);
}
void push(int node,int l,int r){
	if(l==r) return;
	int left=node<<1;
	int right=left|1;
	tree[left].mn=min(tree[node].mn,tree[left].mn);
	tree[left].mn=max(tree[node].mx,tree[left].mn);
	tree[left].mx=min(tree[node].mn,tree[left].mx);
	tree[left].mx=max(tree[node].mx,tree[left].mx);
	tree[right].mn=min(tree[node].mn,tree[right].mn);
	tree[right].mn=max(tree[node].mx,tree[right].mn);
	tree[right].mx=min(tree[node].mn,tree[right].mx);
	tree[right].mx=max(tree[node].mx,tree[right].mx);
	// tree[node].mn=INF;
	// tree[node].mx=-INF;
}
void update(int node,int l,int r,int ql,int qr,int x,int t){
	push(node,l,r);
	if(ql>r||qr<l) return;
	if(ql<=l&&r<=qr){
		if(t){
			tree[node].mn=min(tree[node].mn,x);
			tree[node].mx=min(tree[node].mx,x);
		}
		else{
			tree[node].mn=max(tree[node].mn,x);
			tree[node].mx=max(tree[node].mx,x);
		}
		return;
	}
	tree[node].mn=INF;
	tree[node].mx=-INF;
	int mid=(l+r)/2;
	update(node<<1,l,mid,ql,qr,x,t);
	update(node<<1|1,mid+1,r,ql,qr,x,t);
}
void query(int node,int l,int r,int finalHeight[]){
	if(l==r){
		finalHeight[l-1]=tree[node].mn;
		return;
	}
	push(node,l,r);
	int mid=(l+r)/2;
	query(node<<1,l,mid,finalHeight);
	query(node<<1|1,mid+1,r,finalHeight);
}
void buildWall(int n, int k, int op[], int left[], 
	int right[], int height[], int finalHeight[]){
	// build(1,0,n-1);
	for(int i=0;i<k;i++){
		update(1,1,n,left[i]+1,right[i]+1,height[i],op[i]-1);
	}
	// for(int i=0;i<n;i++){
		// int x=query(1,1,n,i);
		// cout<<x<<" ";
		// finalHeight[i]=x;
	// }
	// cout<<endl;
	query(1,1,n,finalHeight);
	for(int i=0;i<n;i++){
		// cout<<finalHeight[i]<<" ";
	}
	// cout<<endl;
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 112 ms 13992 KB Output is correct
3 Correct 138 ms 7908 KB Output is correct
4 Correct 383 ms 20308 KB Output is correct
5 Correct 263 ms 21400 KB Output is correct
6 Correct 252 ms 19760 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 372 KB Output is correct
4 Correct 5 ms 836 KB Output is correct
5 Correct 4 ms 704 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 121 ms 9332 KB Output is correct
9 Correct 136 ms 5304 KB Output is correct
10 Correct 383 ms 20272 KB Output is correct
11 Correct 260 ms 21528 KB Output is correct
12 Correct 249 ms 19832 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 113 ms 13936 KB Output is correct
15 Correct 23 ms 1984 KB Output is correct
16 Correct 384 ms 20608 KB Output is correct
17 Correct 261 ms 20028 KB Output is correct
18 Correct 256 ms 20040 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 832 KB Output is correct
5 Correct 5 ms 704 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 131 ms 9408 KB Output is correct
9 Correct 137 ms 5332 KB Output is correct
10 Correct 387 ms 20284 KB Output is correct
11 Correct 270 ms 21372 KB Output is correct
12 Correct 252 ms 19828 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 121 ms 13864 KB Output is correct
15 Correct 24 ms 1912 KB Output is correct
16 Correct 394 ms 20564 KB Output is correct
17 Correct 276 ms 19952 KB Output is correct
18 Correct 261 ms 20060 KB Output is correct
19 Correct 618 ms 69508 KB Output is correct
20 Correct 617 ms 67016 KB Output is correct
21 Correct 603 ms 69500 KB Output is correct
22 Correct 581 ms 67112 KB Output is correct
23 Correct 592 ms 67000 KB Output is correct
24 Correct 574 ms 67004 KB Output is correct
25 Correct 594 ms 66888 KB Output is correct
26 Correct 614 ms 69524 KB Output is correct
27 Correct 590 ms 69460 KB Output is correct
28 Correct 590 ms 67016 KB Output is correct
29 Correct 595 ms 66940 KB Output is correct
30 Correct 572 ms 66976 KB Output is correct