oj.uz

Submission #244242

# Submission time Handle Problem Language Result Execution time Memory
244242 2020-07-03T10:01:17 Z tleontest1 Wall (IOI14_wall) C++17
32 / 100
 3000 ms 21112 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;
 
#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];
int cev;
PII lazy[li*4];
 
inline void push(int node,int start,int end){
	if(lazy[node].se==0)return ;
	if(lazy[node].se==1){
		tree[node]=max(tree[node],lazy[node].fi);
	}
	if(lazy[node].se==2){
		tree[node]=min(tree[node],lazy[node].fi);
	}
	if(start!=end){
		if(lazy[node*2].se==lazy[node].se && lazy[node].se==1)lazy[node*2].fi=max(lazy[node*2].fi,lazy[node].fi);
		else if(lazy[node].se==1){
			push(node*2,start,mid);
			lazy[node*2]=lazy[node];
		}
		if(lazy[node*2].se==lazy[node].se && lazy[node].se==2)lazy[node*2].fi=min(lazy[node*2].fi,lazy[node].fi);
		else if(lazy[node].se==2){
			push(node*2,start,mid);
			lazy[node*2]=lazy[node];
		}
		/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		if(lazy[node*2+1].se==lazy[node].se && lazy[node].se==1)lazy[node*2+1].fi=max(lazy[node*2+1].fi,lazy[node].fi);
		else if(lazy[node].se==1){
			push(node*2+1,mid+1,end);
			lazy[node*2+1]=lazy[node];
		}
		if(lazy[node*2+1].se==lazy[node].se && lazy[node].se==2)lazy[node*2+1].fi=min(lazy[node*2+1].fi,lazy[node].fi);
		else if(lazy[node].se==2){
			push(node*2+1,mid+1,end);
			lazy[node*2+1]=lazy[node];
		}
	}
	lazy[node]={0,0};
}
 
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;;
		lazy[node]={val,ty};
		//~ 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]=-1;
		//~ 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 8 ms 384 KB Output is correct
4 Correct 122 ms 888 KB Output is correct
5 Correct 215 ms 888 KB Output is correct
6 Correct 212 ms 872 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 167 ms 8248 KB Output is correct
3 Correct 293 ms 4472 KB Output is correct
4 Correct 938 ms 13756 KB Output is correct
5 Correct 312 ms 14328 KB Output is correct
6 Correct 308 ms 13432 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 8 ms 384 KB Output is correct
4 Correct 131 ms 888 KB Output is correct
5 Correct 216 ms 888 KB Output is correct
6 Correct 212 ms 888 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 172 ms 8188 KB Output is correct
9 Correct 284 ms 4600 KB Output is correct
10 Correct 830 ms 16760 KB Output is correct
11 Correct 318 ms 17272 KB Output is correct
12 Correct 315 ms 20984 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 173 ms 13944 KB Output is correct
15 Correct 1203 ms 2332 KB Output is correct
16 Execution timed out 3080 ms 20984 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 8 ms 384 KB Output is correct
4 Correct 123 ms 888 KB Output is correct
5 Correct 223 ms 888 KB Output is correct
6 Correct 220 ms 888 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 169 ms 8184 KB Output is correct
9 Correct 293 ms 4472 KB Output is correct
10 Correct 843 ms 16760 KB Output is correct
11 Correct 318 ms 17272 KB Output is correct
12 Correct 320 ms 21112 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 177 ms 14048 KB Output is correct
15 Correct 1256 ms 2424 KB Output is correct
16 Execution timed out 3070 ms 20856 KB Time limit exceeded
17 Halted 0 ms 0 KB -