oj.uz

Submission #1031054

# Submission time Handle Problem Language Result Execution time Memory
1031054 2024-07-22T14:01:28 Z tolbi Wall (IOI14_wall) C++17
0 / 100
 281 ms 15192 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];
		}
	}
}
constexpr int MAXN = 2000000;
array<int,2> segtree[MAXN*4];
array<int,2> lazy[MAXN*4];
void upd(array<int,2> &old, array<int,2> &u){
	if (u[0]==0){
		old[1]=min(old[1],u[1]);
		old[0]=min(old[0],old[1]);
	}
	else {
		old[0]=max(old[0],u[0]);
		old[1]=max(old[1],old[0]);
	}
}
struct SegTree{
	int sz;
	SegTree(int n){
		sz=tol(ceil(log2(n)+1))-1;
		fill(segtree,segtree+sz,array<int,2>{0,MOD});
		fill(lazy,lazy+sz,array<int,2>{0,MOD});
	}
	void dallan(int node){
		upd(segtree[node],lazy[node]);
		if (node*2+1<sz){
			if (lazy[node*2+1]!=array<int,2>{0,MOD} && (lazy[node][0]==0)!=(lazy[node*2+1][0]==0)) dallan(node*2+1);
			upd(lazy[node*2+1],lazy[node]);
			if (lazy[node*2+2]!=array<int,2>{0,MOD} && (lazy[node][0]==0)!=(lazy[node*2+1][0]==0)) dallan(node*2+2);
			upd(lazy[node*2+2],lazy[node]);
		}
		lazy[node]={0,MOD};
	}
	void update(int tl, int tr, array<int,2> val, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = sz/2;
		dallan(node);
		if (l>=tl && r<=tr){
			return lazy[node]=val, dallan(node);
		}
		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 = sz/2;
		int node = 0;
		dallan(node);
		while (l<r){
			int mid = l+(r-l)/2;
			if (mid>=x){
				r=mid,node=node*2+1;
			}
			else {
				l=mid+1,node=node*2+2;
			}
			dallan(node);
		}
		return segtree[node][0];
	}
};

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],MOD});
		}
		else {
			segtree.update(left[i],right[i],{0,height[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 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 3 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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