| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 700486 | primenumber_zz | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct LazySegmentTree {
};
void buildWall(int n, int k, vector<int> op, vector<int> left,vector<int> right,vector<int> height, vector<int>finalHeight) {
int MAX = *max_element(height.begin(),height.end());
vector<int>l(n,0),r(n,MAX+1);
vector<array<int,3>>tmp1,tmp2;
for(int i = 0; i < k; i++) {
if(op[i] == 1) {
tmp1.push_back({height[i],1,i});
}
else {
tmp2.push_back({height[i],1,i});
}
}
while(true) {
bool f = false;
for(int i = 0; i < n; i++) {
if(l[i]+1 < r[i]) f = true;
}
if(!f) break;
vector<array<int,3>>q1 = tmp1,q2 = tmp2;
for(int i = 0; i < n; i++) {
if(l[i]+1 < r[i]) {
int mid = (l[i]+r[i])/2;
q1.push_back({mid,0,i});
q2.push_back({mid,0,i});
}
}
sort(q1.rbegin(),q2.rend());
sort(q2.rbegin(),q2.rend());
vector<int>mx1(n),mx2(n);
vector<int>s1(n,-1),s2(n,-1);
{
for(int i = 0; i < n; i++) {
if(q1[i][1] == 0) {
int id = q1[i][2];
for(int j = left[id]; j <= right[id]; j++) {
s1[j] = max(s1[j],i);
}
}
else {
mx1[q1[i][2]] = s1[q1[i][2]];
}
}
}
{
for(int i = 0; i < n; i++) {
if(q2[i][1] == 0) {
int id = q2[i][2];
for(int j = left[id]; j <= right[id]; j++) {
s2[j] = max(s2[j],i);
}
}
else {
mx2[q2[i][2]] = s2[q2[i][2]];
}
}
}
for(int i = 0; i < n; i++) {
if(l[i]+1 < r[i]) {
int mid = (l[i]+r[i])/2;
if(s2[i] < s1[i]) {
l[i] = mid;
}
else {
r[i] = mid;
}
}
}
}
finalHeight = l;
}