Submission #783890

#	Time	Username	Problem	Language	Result	Execution time	Memory
783890		tolbi	Wall (IOI14_wall)	C++17	100 / 100	795 ms	66024 KiB

wall

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
#define author tolbi
#include<bits/stdc++.h>
using namespace std;
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr){return os<<pr.first<<" "<<pr.second;}
ostream& operator<<(ostream& os, bool bl){return os<<(int32_t)bl;}
template<typename X> ostream& operator<<(ostream& os, vector<X> v){for(auto &it : v) os<<it<<" ";return os;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> v){for(auto &it : v) os<<it<<" ";return os;}
#define deci(x) int x;cin>>x;
#define endl '\n'
#define decstr(x) string x;cin>>x;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((int)(bi)))
typedef long long ll;
const ll INF = INT_MAX;
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "wall.h"
struct SegTree{
	vector<pair<int,int>> segtree;
	SegTree(int n){
		segtree.resize(tol(ceil(log2(n)+1))-1,{0,0});
	}
	void update(int tarl, int tarr, pair<int,int> val, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		if (l>tarr || r<tarl) return;
		if (l>=tarl && r<=tarr){
			if (val.first>segtree[node].second){
				segtree[node].second=val.first;
			}
			else if (val.second<segtree[node].first){
				segtree[node].first=val.second;
			}
			segtree[node].first=max(segtree[node].first,val.first);
			segtree[node].second=min(segtree[node].second,val.second);
			return;
		}
		int mid = l+(r-l)/2;
		update(l, mid, segtree[node], l, mid, node*2+1);
		update(mid+1, r, segtree[node], mid+1, r, node*2+2);
		update(tarl, tarr, val, l, mid, node*2+1);
		update(tarl, tarr, val, mid+1, r, node*2+2);
		segtree[node].first=min(segtree[node*2+1].first,segtree[node*2+2].first);
		segtree[node].second=max(segtree[node*2+1].second,segtree[node*2+2].second);
	}
	vector<pair<int,int>> ord;
	void ready(int node = 0, int l = 0, int r = -1){
		if (r==-1) r = segtree.size()/2;
		if (l==r){
			ord.push_back(segtree[node]);
			return;
		}
		int mid = l+(r-l)/2;
		update(l, mid, segtree[node], l, mid, node*2+1);
		update(mid+1, r, segtree[node], mid+1, r, node*2+2);
		ready(node*2+1,l,mid);
		ready(node*2+2,mid+1,r);
	}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegTree segtree(n);
	for (int i = 0; i < k; ++i)
	{
		if (op[i]==1){
			segtree.update(left[i],right[i],{height[i],INF});
		}
		else {	
			segtree.update(left[i],right[i],{-INF,height[i]});
		}
	}
	segtree.ready();
	for (int i = 0; i < n; ++i)
	{
		finalHeight[i]=segtree.ord[i].first;
	}
}

Compilation message (stderr)

wall.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      |

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39