oj.uz

Submission #1102883

# Submission time Handle Problem Language Result Execution time Memory
1102883 2024-10-19T07:28:22 Z ttamx Wall (IOI14_wall) C++17
100 / 100
 1103 ms 86092 KB 
#include "wall.h"
#include<bits/stdc++.h>

using namespace std;

const int K=1<<22;
const int INF=INT_MAX/2;

int n;

struct segtree{
	int t[K],lzmn[K],lzmx[K];
	void apply(int i,int mn,int mx){
		t[i]=min(t[i],mn);
		t[i]=max(t[i],mx);
		lzmn[i]=min(lzmn[i],mn);
		lzmn[i]=max(lzmn[i],mx);
		lzmx[i]=min(lzmx[i],mn);
		lzmx[i]=max(lzmx[i],mx);
	}
	void push(int i){
		apply(i*2,lzmn[i],lzmx[i]);
		apply(i*2+1,lzmn[i],lzmx[i]);
		lzmn[i]=INF,lzmx[i]=-INF;
	}
	void build(int l,int r,int i){
		t[i]=0,lzmn[i]=INF,lzmx[i]=-INF;
		if(l==r)return;
		int m=(l+r)/2;
		build(l,m,i*2);
		build(m+1,r,i*2+1);
	}
	void build(){
		build(0,n-1,1);
	}
	void update(int l,int r,int i,int x,int y,int mn,int mx){
		if(y<l||r<x)return;
		if(x<=l&&r<=y)return apply(i,mn,mx);
		push(i);
		int m=(l+r)/2;
		update(l,m,i*2,x,y,mn,mx);
		update(m+1,r,i*2+1,x,y,mn,mx);
	}
	void update(int x,int y,int mn,int mx){
		update(0,n-1,1,x,y,mn,mx);
	}
	int query(int l,int r,int i,int x){
		if(l==r)return t[i];
		push(i);
		int m=(l+r)/2;
		if(x<=m)return query(l,m,i*2,x);
		else return query(m+1,r,i*2+1,x);
	}
	int query(int x){
		return query(0,n-1,1,x);
	}
}s;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	::n=n;
	s.build();
	for(int i=0;i<k;i++){
		s.update(0,n-1,1,left[i],right[i],op[i]==2?height[i]:INF,op[i]==1?height[i]:-INF);
	}
	for(int i=0;i<n;i++){
		finalHeight[i]=s.query(i);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4436 KB Output is correct
2 Correct 3 ms 4436 KB Output is correct
3 Correct 2 ms 4436 KB Output is correct
4 Correct 7 ms 4692 KB Output is correct
5 Correct 6 ms 4692 KB Output is correct
6 Correct 6 ms 4692 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4436 KB Output is correct
2 Correct 96 ms 18184 KB Output is correct
3 Correct 121 ms 17868 KB Output is correct
4 Correct 371 ms 28708 KB Output is correct
5 Correct 253 ms 29772 KB Output is correct
6 Correct 259 ms 28236 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 3 ms 4692 KB Output is correct
3 Correct 3 ms 4436 KB Output is correct
4 Correct 8 ms 4748 KB Output is correct
5 Correct 7 ms 4692 KB Output is correct
6 Correct 6 ms 4704 KB Output is correct
7 Correct 1 ms 4436 KB Output is correct
8 Correct 93 ms 17996 KB Output is correct
9 Correct 141 ms 18008 KB Output is correct
10 Correct 433 ms 28748 KB Output is correct
11 Correct 248 ms 29772 KB Output is correct
12 Correct 239 ms 28236 KB Output is correct
13 Correct 1 ms 4436 KB Output is correct
14 Correct 96 ms 18252 KB Output is correct
15 Correct 23 ms 11876 KB Output is correct
16 Correct 362 ms 29012 KB Output is correct
17 Correct 253 ms 28492 KB Output is correct
18 Correct 240 ms 28496 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 2 ms 4688 KB Output is correct
4 Correct 6 ms 4692 KB Output is correct
5 Correct 6 ms 4856 KB Output is correct
6 Correct 6 ms 4692 KB Output is correct
7 Correct 1 ms 4436 KB Output is correct
8 Correct 90 ms 18188 KB Output is correct
9 Correct 124 ms 17996 KB Output is correct
10 Correct 398 ms 28748 KB Output is correct
11 Correct 276 ms 29796 KB Output is correct
12 Correct 253 ms 28168 KB Output is correct
13 Correct 1 ms 4436 KB Output is correct
14 Correct 92 ms 17992 KB Output is correct
15 Correct 26 ms 11860 KB Output is correct
16 Correct 410 ms 29212 KB Output is correct
17 Correct 250 ms 28492 KB Output is correct
18 Correct 391 ms 28492 KB Output is correct
19 Correct 1040 ms 85836 KB Output is correct
20 Correct 1098 ms 83468 KB Output is correct
21 Correct 1010 ms 85888 KB Output is correct
22 Correct 983 ms 83500 KB Output is correct
23 Correct 996 ms 83532 KB Output is correct
24 Correct 944 ms 83564 KB Output is correct
25 Correct 1022 ms 83380 KB Output is correct
26 Correct 1018 ms 86092 KB Output is correct
27 Correct 1103 ms 86048 KB Output is correct
28 Correct 1034 ms 83532 KB Output is correct
29 Correct 1059 ms 83588 KB Output is correct
30 Correct 1010 ms 83476 KB Output is correct