oj.uz

Submission #287113

# Submission time Handle Problem Language Result Execution time Memory
287113 2020-08-31T11:55:19 Z AKaan37 Wall (IOI14_wall) C++17
100 / 100
 1400 ms 93304 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 = 2000005;
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 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 10 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 7 ms 896 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 178 ms 8184 KB Output is correct
3 Correct 257 ms 4472 KB Output is correct
4 Correct 786 ms 12616 KB Output is correct
5 Correct 364 ms 12920 KB Output is correct
6 Correct 352 ms 13048 KB Output is correct

Subtask #3
29.0 / 29.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 11 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 179 ms 8184 KB Output is correct
9 Correct 256 ms 4600 KB Output is correct
10 Correct 794 ms 12368 KB Output is correct
11 Correct 393 ms 12920 KB Output is correct
12 Correct 345 ms 13016 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 180 ms 8184 KB Output is correct
15 Correct 53 ms 1784 KB Output is correct
16 Correct 1006 ms 12664 KB Output is correct
17 Correct 377 ms 12792 KB Output is correct
18 Correct 365 ms 12664 KB Output is correct

Subtask #4
39.0 / 39.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 10 ms 896 KB Output is correct
5 Correct 8 ms 896 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 181 ms 8184 KB Output is correct
9 Correct 259 ms 4600 KB Output is correct
10 Correct 798 ms 12536 KB Output is correct
11 Correct 366 ms 13048 KB Output is correct
12 Correct 349 ms 12920 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 180 ms 8184 KB Output is correct
15 Correct 52 ms 1784 KB Output is correct
16 Correct 1035 ms 12700 KB Output is correct
17 Correct 391 ms 12704 KB Output is correct
18 Correct 366 ms 12664 KB Output is correct
19 Correct 1400 ms 90564 KB Output is correct
20 Correct 1329 ms 90616 KB Output is correct
21 Correct 1351 ms 93304 KB Output is correct
22 Correct 1335 ms 90616 KB Output is correct
23 Correct 1337 ms 90616 KB Output is correct
24 Correct 1322 ms 90564 KB Output is correct
25 Correct 1327 ms 90492 KB Output is correct
26 Correct 1369 ms 93108 KB Output is correct
27 Correct 1338 ms 93176 KB Output is correct
28 Correct 1347 ms 90760 KB Output is correct
29 Correct 1329 ms 90600 KB Output is correct
30 Correct 1352 ms 90416 KB Output is correct