Submission #968916

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
968916	2024-04-24T09:32:15 Z	elotelo966	Wall (IOI14_wall)	C++17	8 / 100	3000 ms	13960 KB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mid (start+end)/2

pair<int,int> lazy[8000000];
int fin[2000000];

inline void push(int node,int start,int end){
	if(lazy[node].fi==0 && lazy[node].se==0)return ;
	if(start!=end){
		push(node*2,start,mid),push(node*2+1,mid+1,end);
		lazy[node*2]=lazy[node];
		lazy[node*2+1]=lazy[node];
	}
	else{
		if(lazy[node].fi==1)fin[start]=max(fin[start],lazy[node].se);
		else fin[start]=min(fin[start],lazy[node].se);
	}
	lazy[node]=make_pair(0,0);
}

inline void update(int node,int start,int end,int l,int r,int val,int sem){
	if(start>end || start>r || end<l)return ;
	push(node,start,end);
	if(start>=l && end<=r){
		lazy[node]=make_pair(sem,val);
		push(node,start,end);
		return ;
	}
	update(node*2,start,mid,l,r,val,sem),update(node*2+1,mid+1,end,l,r,val,sem);
}

inline void finish(int node,int start,int end){
	push(node,start,end);
	if(start==end)return ;
	finish(node*2,start,mid),finish(node*2+1,mid+1,end);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0;i<k;i++){
		if(op[i]==1){
			update(1,0,n-1,left[i],right[i],height[i],1);
		}
		else{
			update(1,0,n-1,left[i],right[i],height[i],-1);
		}
	}
	
	finish(1,0,n-1);
	
	for(int i=0;i<n;i++){
		finalHeight[i]=fin[i];
	}
	
	return;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	2 ms	348 KB	Output is correct
3	Correct	3 ms	348 KB	Output is correct
4	Correct	89 ms	924 KB	Output is correct
5	Correct	82 ms	860 KB	Output is correct
6	Correct	91 ms	924 KB	Output is correct

Subtask #2

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	117 ms	13960 KB	Output is correct
3	Execution timed out	3094 ms	6736 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	3 ms	348 KB	Output is correct
4	Correct	90 ms	944 KB	Output is correct
5	Correct	84 ms	924 KB	Output is correct
6	Correct	87 ms	924 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	113 ms	13908 KB	Output is correct
9	Execution timed out	3049 ms	8036 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-

Subtask #4

0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	2 ms	348 KB	Output is correct
3	Correct	3 ms	516 KB	Output is correct
4	Correct	89 ms	940 KB	Output is correct
5	Correct	83 ms	924 KB	Output is correct
6	Correct	90 ms	924 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	118 ms	13844 KB	Output is correct
9	Execution timed out	3018 ms	8020 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-