| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 700486 | primenumber_zz | Wall (IOI14_wall) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}