oj.uz

Submission #287111

# Submission time Handle Problem Language Result Execution time Memory
287111 2020-08-31T11:54:36 Z AKaan37 Wall (IOI14_wall) C++17
61 / 100
 1175 ms 41208 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]);
	if(start!=end){
		lazy[node*2] = max(lazy[node*2],lazy[node]),lazy1[node*2] = max(lazy1[node*2],lazy[node]);
        lazy[node*2+1] = max(lazy[node*2+1],lazy[node]),lazy1[node*2+1] = max(lazy1[node*2+1],lazy[node]);
        lazy1[node*2] = min(lazy1[node*2],lazy1[node]),lazy[node*2] = min(lazy[node*2],lazy1[node]);
        lazy1[node*2+1] = min(lazy1[node*2+1],lazy1[node]),lazy[node*2+1] = min(lazy[node*2+1],lazy1[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){
		lazy[node*2] = max(lazy[node*2],lazy[node]),lazy1[node*2] = max(lazy1[node*2],lazy[node]);
        lazy[node*2+1] = max(lazy[node*2+1],lazy[node]),lazy1[node*2+1] = max(lazy1[node*2+1],lazy[node]);
        lazy1[node*2] = min(lazy1[node*2],lazy1[node]),lazy[node*2] = min(lazy[node*2],lazy1[node]);
        lazy1[node*2+1] = min(lazy1[node*2+1],lazy1[node]),lazy[node*2+1] = min(lazy[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;
		
		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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 18 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 179 ms 8184 KB Output is correct
3 Correct 256 ms 4600 KB Output is correct
4 Correct 858 ms 12408 KB Output is correct
5 Correct 368 ms 12920 KB Output is correct
6 Correct 347 ms 13048 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 11 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 9 ms 1024 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 179 ms 10584 KB Output is correct
9 Correct 314 ms 6952 KB Output is correct
10 Correct 884 ms 15188 KB Output is correct
11 Correct 413 ms 15756 KB Output is correct
12 Correct 355 ms 15864 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 187 ms 11256 KB Output is correct
15 Correct 60 ms 2300 KB Output is correct
16 Correct 1175 ms 15568 KB Output is correct
17 Correct 397 ms 15652 KB Output is correct
18 Correct 395 ms 15584 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 11 ms 1024 KB Output is correct
5 Correct 15 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 177 ms 10748 KB Output is correct
9 Correct 257 ms 7032 KB Output is correct
10 Correct 841 ms 15260 KB Output is correct
11 Correct 384 ms 15736 KB Output is correct
12 Correct 359 ms 15672 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 182 ms 10872 KB Output is correct
15 Correct 52 ms 2296 KB Output is correct
16 Correct 1027 ms 15312 KB Output is correct
17 Correct 363 ms 15480 KB Output is correct
18 Correct 362 ms 15356 KB Output is correct
19 Runtime error 240 ms 41208 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -