oj.uz

Submission #287093

# Submission time Handle Problem Language Result Execution time Memory
287093 2020-08-31T11:44:14 Z AKaan37 Wall (IOI14_wall) C++17
24 / 100
 625 ms 15352 KB 
//Bismillahirrahmanirrahim

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

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 2000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 200005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,tree[li*4],lazy[li*4],lazy1[li*4];
int cev;
string s;
vector<int> v;

inline void push1(int node,int start,int end){
	//~ if(start==end)cout<<lazy[node]<<"**\n";
	if(lazy[node]==0)return;
	tree[node]=max(tree[node],lazy[node]);
	//~ cout<
	if(lazy[node]>lazy1[node])lazy1[node]=inf;
	if(start!=end){
		lazy[node*2]=max(lazy[node*2],lazy[node]);
		lazy[node*2+1]=max(lazy[node*2+1],lazy[node]);
	}
	lazy[node]=0;
}

inline void push2(int node,int start,int end){
	//~ cout<<lazy1[node]<<endl;
	if(lazy1[node]==inf)return;
	tree[node]=min(tree[node],lazy1[node]);
	if(lazy[node]>lazy1[node])lazy[node]=lazy1[node];
	if(start!=end){
		lazy1[node*2]=min(lazy1[node*2],lazy1[node]);
		lazy1[node*2+1]=min(lazy1[node*2+1],lazy1[node]);
	}
	lazy1[node]=inf;
}

inline void update(int node,int start,int end,int l,int r,int val){
	push2(node,start,end);push1(node,start,end);
	
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){
		lazy[node]=val;
		//~ cout<<val<<endl;
		push1(node,start,end);
		return ;
	}
	update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
	tree[node]=max(tree[node*2],tree[node*2+1]);
}

inline void update1(int node,int start,int end,int l,int r,int val){
	push2(node,start,end);push1(node,start,end);
	
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){
		lazy1[node]=val;
		push2(node,start,end);
		return ;
	}
	update1(node*2,start,mid,l,r,val),update1(node*2+1,mid+1,end,l,r,val);
	tree[node]=max(tree[node*2],tree[node*2+1]);
}

inline int query(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return 0;
	push2(node,start,end);push1(node,start,end);
	
	if(start>=l && end<=r)return tree[node];
	return max(query(node*2,start,mid,l,r),query(node*2+1,mid+1,end,l,r));
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=1;i<=n*4;i++){
		lazy1[i]=inf;
	}
	for(int i=0;i<k;i++){
		if(op[i]==1){
			update(1,1,n,left[i]+1,right[i]+1,height[i]);
		}
		else update1(1,1,n,left[i]+1,right[i]+1,height[i]);
	}
	//~ cout<<query(1,1,n,1,1);
	FOR finalHeight[i-1]=query(1,1,n,i,i);
	return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 173 ms 10432 KB Output is correct
3 Correct 228 ms 6888 KB Output is correct
4 Correct 625 ms 14840 KB Output is correct
5 Correct 359 ms 15352 KB Output is correct
6 Correct 353 ms 15312 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -