oj.uz

Submission #783890

# Submission time Handle Problem Language Result Execution time Memory
783890 2023-07-15T11:49:17 Z tolbi Wall (IOI14_wall) C++17
100 / 100
 795 ms 66024 KB 
#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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 5 ms 1012 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 110 ms 8732 KB Output is correct
3 Correct 242 ms 5068 KB Output is correct
4 Correct 484 ms 12324 KB Output is correct
5 Correct 353 ms 12352 KB Output is correct
6 Correct 366 ms 12356 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 960 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 8 ms 980 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 132 ms 8724 KB Output is correct
9 Correct 199 ms 5148 KB Output is correct
10 Correct 537 ms 12356 KB Output is correct
11 Correct 349 ms 12356 KB Output is correct
12 Correct 330 ms 12356 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 121 ms 8716 KB Output is correct
15 Correct 31 ms 2228 KB Output is correct
16 Correct 583 ms 12352 KB Output is correct
17 Correct 316 ms 12272 KB Output is correct
18 Correct 327 ms 12472 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 952 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 109 ms 8752 KB Output is correct
9 Correct 175 ms 5180 KB Output is correct
10 Correct 499 ms 12352 KB Output is correct
11 Correct 320 ms 12472 KB Output is correct
12 Correct 309 ms 12360 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 112 ms 8772 KB Output is correct
15 Correct 30 ms 2228 KB Output is correct
16 Correct 530 ms 12476 KB Output is correct
17 Correct 319 ms 12360 KB Output is correct
18 Correct 315 ms 12356 KB Output is correct
19 Correct 748 ms 65964 KB Output is correct
20 Correct 795 ms 65880 KB Output is correct
21 Correct 727 ms 65904 KB Output is correct
22 Correct 720 ms 65876 KB Output is correct
23 Correct 736 ms 65900 KB Output is correct
24 Correct 723 ms 65892 KB Output is correct
25 Correct 718 ms 66024 KB Output is correct
26 Correct 763 ms 65872 KB Output is correct
27 Correct 766 ms 65892 KB Output is correct
28 Correct 728 ms 65960 KB Output is correct
29 Correct 723 ms 65920 KB Output is correct
30 Correct 721 ms 65940 KB Output is correct