oj.uz

Submission #1030888

# Submission time Handle Problem Language Result Execution time Memory
1030888 2024-07-22T11:25:20 Z tolbi Wall (IOI14_wall) C++17
24 / 100
 344 ms 22720 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1e9+7;
#define tol(bi) (1LL<<((int)(bi)))
void _upd(array<int,4> &old, array<int,3> upd){
	if (upd[1]==1){
		if (old[0]<=upd[0]){
			old[0]=min(old[2],max(old[0],upd[0]));
			old[1]=upd[2];
		}
	}
	else {
		if (old[2]>=upd[0]){
			old[2]=max(old[0],min(old[2],upd[0]));
			old[3]=upd[2];
		}
	}
}
struct SegTree{
	vector<array<int,4>> segtree;
	SegTree(int n){
		segtree.resize(tol(ceil(log2(n)+1))-1,{0,MOD,MOD,MOD});
	}
	void update(int tl, int tr, array<int,3> val, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		if (l>=tl && r<=tr){
			_upd(segtree[node],val);
			return;
		}
		if (l>tr || r<tl) return;
		int mid = l+(r-l)/2;
		if (tl<=mid) update(tl, tr, val, l, mid, node*2+1);
		if (mid<tr) update(tl, tr, val, mid+1, r, node*2+2);
	}
	int query(int x){
		int l = 0, r = segtree.size()/2;
		int node = 0;
		array<int,4> pr = {0,MOD,MOD,MOD};
		vector<array<int,3>> upds;
		upds.push_back({segtree[node][0],1,segtree[node][1]});
		upds.push_back({segtree[node][2],2,segtree[node][3]});
		while (l<r){
			int mid = l+(r-l)/2;
			if (x<=mid){
				r=mid;
				node=node*2+1;
			}
			else {
				l=mid+1;
				node=node*2+2;
			}
			upds.push_back({segtree[node][0],1,segtree[node][1]});
			upds.push_back({segtree[node][2],2,segtree[node][3]});
		}
		sort(upds.begin(), upds.end(), [&](array<int,3> &a, array<int,3> &b){
			return a[2]>b[2];
		});
		for (auto &it : upds){
			_upd(pr,it);
		}
		return pr[0];
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegTree segtree(n);
	for (int i = k-1; i >= 0; i--){
		segtree.update(left[i],right[i],{height[i],op[i],i});
	}
	for (int i = 0; i < n; ++i)
	{
		finalHeight[i]=segtree.query(i);
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 91 ms 13912 KB Output is correct
3 Correct 103 ms 8540 KB Output is correct
4 Correct 344 ms 22224 KB Output is correct
5 Correct 198 ms 22720 KB Output is correct
6 Correct 217 ms 21332 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 568 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -