oj.uz

Submission #1031050

# Submission time Handle Problem Language Result Execution time Memory
1031050 2024-07-22T14:00:18 Z tolbi Wall (IOI14_wall) C++17
8 / 100
 3000 ms 16136 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}) dallan(node*2+1);
			upd(lazy[node*2+1],lazy[node]);
			if (lazy[node*2+2]!=array<int,2>{0,MOD}) 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 5 ms 528 KB Output is correct
4 Correct 282 ms 1160 KB Output is correct
5 Correct 256 ms 1116 KB Output is correct
6 Correct 286 ms 1156 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 84 ms 12868 KB Output is correct
3 Execution timed out 3081 ms 8532 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.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 Correct 5 ms 2504 KB Output is correct
4 Correct 313 ms 2932 KB Output is correct
5 Correct 266 ms 2952 KB Output is correct
6 Correct 257 ms 2948 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 87 ms 15944 KB Output is correct
9 Execution timed out 3026 ms 10068 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 6 ms 2396 KB Output is correct
4 Correct 286 ms 2944 KB Output is correct
5 Correct 292 ms 4956 KB Output is correct
6 Correct 277 ms 2940 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 128 ms 16136 KB Output is correct
9 Execution timed out 3064 ms 11708 KB Time limit exceeded
10 Halted 0 ms 0 KB -