oj.uz

Submission #244251

# Submission time Handle Problem Language Result Execution time Memory
244251 2020-07-03T11:41:28 Z tleontest1 Wall (IOI14_wall) C++14
100 / 100
 1627 ms 115128 KB 
#include "wall.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long lo;
typedef pair< int,int > PII;
typedef pair< int,PII > PIII;
 
#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 int inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 2000005;
const lo mod = 1000000007;
 
int flag,t,m,tree[li*4],lazy1[li*4],lazy[li*4];
int cev;
//~ PIII lazy[li*4];
 
inline void push(int node,int start,int end){
	if(start==end){tree[node]=max(tree[node],lazy[node]);}
	if(start==end){tree[node]=min(tree[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]);
	}
	lazy[node]=-inf;
	lazy1[node]=inf;
}
 
inline void update(int node,int start,int end,int l,int r,int val,int ty){
	//~ push1(node,start,end);
	push(node,start,end);
	if(start>end || start>r || end<l)return ;
	
	if(start>=l && end<=r){
		//~ cout<<query1(1,1,m,start,start)<<" : : "<<query1(1,1,m,end,end)<<" : : "<<start<<" ; : "<<end<<endl;;
		if(ty==1)lazy[node]=max(val,lazy[node]);
		if(ty==2)lazy1[node]=min(lazy1[node],val);
		//~ push1(node,start,end);
		push(node,start,end);
		return ;
	}
	update(node*2,start,mid,l,r,val,ty);
	update(node*2+1,mid+1,end,l,r,val,ty);
	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;
	push(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[]){
	m=n;
	for(int i=1;i<=4*n;i++){
		//~ tree1[i]=inf;
		lazy1[i]=inf;
		//~ tree[i]=-1;
		lazy[i]=-inf;
		//~ tree2[i]=inf;
		//~ lazy2[i]=inf;
	}
	//~ int mn=inf;
	//~ for(int i=k-1;i>=0;i--){
		//~ if(op[i]==1)
		//~ update2(1,1,n,left[i],right[i],i);
	//~ }
	//~ FOR{
		//~ int at=query2(1,1,n,i,i);
		//~ cout<<i<<" : : "<<at<<endl;
		//~ if(at==inf)continue;
		//~ v[at].pb(i);
	//~ }
	for(int i=0;i<k;i++){
		//~ cout<<height[i]<<endl;
		//~ if(op[i]==2){
			//~ update1(1,1,n,left[i]+1,right[i]+1,height[i]);
			//~ continue;
		//~ }
		//~ cout<<"**\n";
		update(1,1,n,left[i]+1,right[i]+1,height[i],op[i]);
		//~ for(int j=0;j<(int)v[i].size();j++){
			//~ cout<<v[i][j]<<endl;
		//~ }
		//~ if(op[i]==2)update1(1,1,n,left[i]+1,right[i]+1,height[i]);
		//~ update2(1,1,n,left[i]+1,right[i]+1,i);
	}
	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 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 13 ms 1024 KB Output is correct
5 Correct 12 ms 1024 KB Output is correct
6 Correct 13 ms 896 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 174 ms 8184 KB Output is correct
3 Correct 260 ms 4600 KB Output is correct
4 Correct 742 ms 12920 KB Output is correct
5 Correct 465 ms 13432 KB Output is correct
6 Correct 442 ms 13432 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 13 ms 1024 KB Output is correct
5 Correct 13 ms 1024 KB Output is correct
6 Correct 12 ms 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 180 ms 8184 KB Output is correct
9 Correct 260 ms 4600 KB Output is correct
10 Correct 736 ms 12920 KB Output is correct
11 Correct 430 ms 13432 KB Output is correct
12 Correct 435 ms 13560 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 174 ms 8184 KB Output is correct
15 Correct 47 ms 1912 KB Output is correct
16 Correct 726 ms 13240 KB Output is correct
17 Correct 442 ms 22364 KB Output is correct
18 Correct 453 ms 22264 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 13 ms 1024 KB Output is correct
5 Correct 12 ms 896 KB Output is correct
6 Correct 12 ms 896 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 173 ms 8184 KB Output is correct
9 Correct 256 ms 4600 KB Output is correct
10 Correct 746 ms 13052 KB Output is correct
11 Correct 448 ms 13488 KB Output is correct
12 Correct 443 ms 13432 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 176 ms 8160 KB Output is correct
15 Correct 47 ms 1784 KB Output is correct
16 Correct 735 ms 13176 KB Output is correct
17 Correct 450 ms 22264 KB Output is correct
18 Correct 450 ms 22264 KB Output is correct
19 Correct 1575 ms 114840 KB Output is correct
20 Correct 1564 ms 112504 KB Output is correct
21 Correct 1627 ms 114872 KB Output is correct
22 Correct 1563 ms 112668 KB Output is correct
23 Correct 1550 ms 112528 KB Output is correct
24 Correct 1558 ms 112328 KB Output is correct
25 Correct 1566 ms 112276 KB Output is correct
26 Correct 1567 ms 115128 KB Output is correct
27 Correct 1615 ms 114928 KB Output is correct
28 Correct 1594 ms 112504 KB Output is correct
29 Correct 1564 ms 112376 KB Output is correct
30 Correct 1585 ms 112380 KB Output is correct