oj.uz

Submission #1086515

# Submission time Handle Problem Language Result Execution time Memory
1086515 2024-09-10T20:58:38 Z EkinOnal Wall (IOI14_wall) C++17
100 / 100
 486 ms 177676 KB 
//#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include "wall.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
 
#define MAX 2000005
#define pb push_back
#define mp make_pair 
#define int long long
#define f first
#define s second
#define vi vector<int>
#define pii pair<int,int>
#define si set<int>
#define vpii vector<pair<int,int>> 
const int mod = 1e9+7;
const int INF = 1e18;
// myMap.begin()->first :  key
// myMap.begin()->second : value
 
int epow(int a,int b){int ans=1;while(b){if(b&1) ans*=a;a*=a;b>>=1;ans%=mod;a%=mod;}return (ans+mod)%mod;}
int gcd(int a,int b) {if(a<b)swap(a,b);while(b){int tmp=b;b=a%b;a=tmp;}return a;}
int mul(int a,int b){return ((a%mod)*(b%mod))%mod;}
int sum(int a,int b){return ((a%mod)+(b%mod))%mod;}

// typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
// typedef 
// tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_multiset;

int n,d;
vi arr(MAX);

struct segItem{
	int val,lazymin,lazymax;
};

struct SegTree{
//	segItem tree[MAX*4];
	int mn[MAX*4],mx[MAX*4];

	SegTree(){
		memset(mn,-1,sizeof(mn));
		memset(mx,-1,sizeof(mx));
	}

	void push(int v){
		if(mn[v]!=-1){
			if(mn[v*2]==-1) mn[v*2]=mn[v];
			else mn[v*2]=max(mn[v*2],mn[v]);

			if(mn[v*2+1]==-1) mn[v*2+1]=mn[v];
			else mn[v*2+1]=max(mn[v*2+1],mn[v]);

			if(mx[v*2]!=-1) mx[v*2]=max(mx[v*2],mn[v]);
			if(mx[v*2+1]!=-1) mx[v*2+1]=max(mx[v*2+1],mn[v]);

		}
		if(mx[v]!=-1){
			if(mx[v*2]==-1) mx[v*2]=mx[v];
			else mx[v*2]=min(mx[v*2],mx[v]);

			if(mx[v*2+1]==-1) mx[v*2+1]=mx[v];
			else mx[v*2+1]=min(mx[v*2+1],mx[v]);

			if(mn[v*2]!=-1) mn[v*2]=min(mn[v*2],mx[v]);
			if(mn[v*2+1]!=-1) mn[v*2+1]=min(mn[v*2+1],mx[v]);
		}
		mn[v]=mx[v]=-1;
	}

	void updatemax(int v,int tl,int tr,int l ,int r,int val){
		if(tl>tr || tl>r || tr<l) return;
		if(tl>=l && tr<=r){
			if(mx[v]==-1) mx[v]=val;
			else mx[v]=min(mx[v],val);
			if(mn[v]!=-1) mn[v]=min(mn[v],val); 
			return;
		}
		push(v);
		int mid=(tl+tr)>>1;
		updatemax(v*2,tl,mid,l,r,val); updatemax(v*2+1,mid+1,tr,l,r,val);
	}

	void updatemin(int v,int tl,int tr,int l ,int r,int val){
		if(tl>tr || tl>r || tr<l) return;
		if(tl>=l && tr<=r){
			if(mn[v]==-1) mn[v]=val;
			else mn[v]=max(mn[v],val);
			if(mx[v]!=-1) mx[v]=max(mx[v],val); 
			return;
		}
		push(v); 
		int mid=(tl+tr)>>1;
		updatemin(v*2,tl,mid,l,r,val); updatemin(v*2+1,mid+1,tr,l,r,val);
	}

	void query(int v,int tl,int tr){
		if(tl==tr) {arr[tl-1]=max(mn[v],0LL);return;}
		int mid=(tl+tr)>>1;
		push(v);
		query(v*2,tl,mid); query(v*2+1,mid+1,tr);
	}

};

SegTree segtree;

void buildWall(int32_t N, int32_t k, int32_t op[], int32_t left[], int32_t right[], int32_t height[], int32_t finalHeight[]){
    n = N;
 
   for(int i=0;i<k;i++){
		if(op[i]==1) segtree.updatemin(1,1,n,left[i]+1,right[i]+1,height[i]);
		else segtree.updatemax(1,1,n,left[i]+1,right[i]+1,height[i]);
	}
// 	arr.resize(n);
   segtree.query(1,1,n);
   for(int i=0;i<n;i++) finalHeight[i]=arr[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 141140 KB Output is correct
2 Correct 55 ms 141396 KB Output is correct
3 Correct 56 ms 141136 KB Output is correct
4 Correct 60 ms 141396 KB Output is correct
5 Correct 60 ms 141436 KB Output is correct
6 Correct 61 ms 141396 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 141136 KB Output is correct
2 Correct 135 ms 155004 KB Output is correct
3 Correct 178 ms 148248 KB Output is correct
4 Correct 416 ms 159188 KB Output is correct
5 Correct 232 ms 160316 KB Output is correct
6 Correct 217 ms 158700 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 141140 KB Output is correct
2 Correct 61 ms 141396 KB Output is correct
3 Correct 70 ms 141140 KB Output is correct
4 Correct 65 ms 141392 KB Output is correct
5 Correct 60 ms 141396 KB Output is correct
6 Correct 65 ms 141396 KB Output is correct
7 Correct 61 ms 141140 KB Output is correct
8 Correct 148 ms 154792 KB Output is correct
9 Correct 187 ms 148300 KB Output is correct
10 Correct 442 ms 159316 KB Output is correct
11 Correct 233 ms 160336 KB Output is correct
12 Correct 231 ms 158804 KB Output is correct
13 Correct 58 ms 141140 KB Output is correct
14 Correct 151 ms 154768 KB Output is correct
15 Correct 84 ms 142416 KB Output is correct
16 Correct 483 ms 159444 KB Output is correct
17 Correct 229 ms 158804 KB Output is correct
18 Correct 228 ms 159060 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 141100 KB Output is correct
2 Correct 63 ms 141392 KB Output is correct
3 Correct 60 ms 141140 KB Output is correct
4 Correct 64 ms 141392 KB Output is correct
5 Correct 59 ms 141392 KB Output is correct
6 Correct 64 ms 141468 KB Output is correct
7 Correct 57 ms 141136 KB Output is correct
8 Correct 152 ms 154960 KB Output is correct
9 Correct 183 ms 148308 KB Output is correct
10 Correct 430 ms 159316 KB Output is correct
11 Correct 238 ms 160336 KB Output is correct
12 Correct 234 ms 158804 KB Output is correct
13 Correct 61 ms 141136 KB Output is correct
14 Correct 147 ms 154960 KB Output is correct
15 Correct 84 ms 142420 KB Output is correct
16 Correct 486 ms 159572 KB Output is correct
17 Correct 224 ms 158804 KB Output is correct
18 Correct 217 ms 158984 KB Output is correct
19 Correct 465 ms 177492 KB Output is correct
20 Correct 442 ms 174956 KB Output is correct
21 Correct 467 ms 177616 KB Output is correct
22 Correct 433 ms 175184 KB Output is correct
23 Correct 442 ms 175204 KB Output is correct
24 Correct 439 ms 175188 KB Output is correct
25 Correct 450 ms 175184 KB Output is correct
26 Correct 467 ms 177488 KB Output is correct
27 Correct 433 ms 177676 KB Output is correct
28 Correct 451 ms 175188 KB Output is correct
29 Correct 458 ms 175064 KB Output is correct
30 Correct 439 ms 175076 KB Output is correct