이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
using namespace std;
#include "wall.h"
const int S = (1 << (int)ceil(log2(2e6)));
vector<int> L(S*2, 0);
vector<int> R(S*2, INT_MAX);
void push(int j){
if(j < S){
if(L[j] == R[j]){
L[j*2] = R[j*2] = L[j*2+1] = R[j*2+1] = L[j];
}
else{
if(L[j*2] == R[j*2]){
if(R[j] < L[j*2]) L[j*2] = R[j*2] = R[j];
if(L[j] > L[j*2]) L[j*2] = R[j*2] = L[j];
}
else if(R[j] < L[j*2]){
L[j*2] = R[j*2] = R[j];
}
else if(L[j] > R[j*2]){
L[j*2] = R[j*2] = L[j];
}
else{
R[j*2] = min(R[j*2], R[j]);
L[j*2] = max(L[j*2], L[j]);
}
if(L[j*2+1] == R[j*2+1]){
if(R[j] < L[j*2+1]) L[j*2+1] = R[j*2+1] = R[j];
if(L[j] > L[j*2+1]) L[j*2+1] = R[j*2+1] = L[j];
}
else if(R[j] < L[j*2+1]){
L[j*2+1] = R[j*2+1] = R[j];
}
else if(L[j] > R[j*2+1]){
L[j*2+1] = R[j*2+1] = L[j];
}
else{
R[j*2+1] = min(R[j*2+1], R[j]);
L[j*2+1] = max(L[j*2+1], L[j]);
}
}
L[j] = 0, R[j] = INT_MAX;
}
}
void rangeupdate(int j, int x, int y, int l, int r, int t, int v){
if(y < l || r < x) return;
push(j);
if(l <= x && y <= r){
if(t == 1){
L[j] = max(L[j], v);
R[j] = max(R[j], v);
}
else{
L[j] = min(L[j], v);
R[j] = min(R[j], v);
}
return;
}
rangeupdate(j*2,x,(x+y)/2,l,r,t,v);
rangeupdate(j*2+1,(x+y)/2+1,y,l,r,t,v);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 0; i < k; i++){
rangeupdate(1,0,S-1,left[i],right[i],op[i], height[i]);
}
for(int i = 1; i < S; i++) push(i);
for(int i = 0; i < n; i++){
finalHeight[i] = L[S + i];
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |