| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 541323 | starchan | Wall (IOI14_wall) | C++17 | 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>
#include "wall.h"
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF 1e17
#define zero (int)0
#define MX (int)3e5+5
#define LMX (int)500
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
const int mod = 1e9+7; //may change to that 99.. number.
struct mx_mn_iser_segment_tree
{
vector<int> smx;
vector<int> mx;
vector<int> smn;
vector<int> mn;
vector<int> mxlazy;
vector<int> mnlazy;
void init()
{
smx.assign(LMX, -INF);
mx.assign(LMX, 0);
smn.assign(LMX, INF);
mn.assign(LMX, 0);
mxlazy.assign(LMX, -INF);
mnlazy.assign(LMX, INF);
}
void mx_push(int id)
{
if(mn[2*id] == mn[id])
mnlazy[2*id] = max(mnlazy[2*id], mnlazy[id]);
if(mn[2*id+1] == mn[id])
mnlazy[2*id+1] = max(mnlazy[2*id+1], mnlazy[id]);
mnlazy[id] = -INF;
return;
}
void mn_push(int id)
{
if(mx[2*id] == mx[id])
mxlazy[2*id] = min(mxlazy[2*id], mxlazy[id]);
if(mx[2*id+1] == mx[id])
mxlazy[2*id+1] = min(mxlazy[2*id+1], mxlazy[id]);
mxlazy[id] = INF;
return;
}
int fix(int id)
{
mn[id] = min(mn[2*id], mn[2*id+1]);
int turbo1 = min(smn[2*id], smn[2*id+1]);
if(mn[2*id]==mn[2*id+1])
smn[id] = turbo1;
else
smn[id] = min(mn[2*id]+mn[2*id+1]-mn[id], turbo1);
mx[id] = max(mx[2*id], mx[2*id+1]);
int turbo2 = max(smx[2*id], smx[2*id+1]);
if(mx[2*id]==mx[2*id+1])
smx[id] = turbo2;
else
smx[id] = max(mx[2*id]+mx[2*id+1]-mx[id], turbo2);
}
void mx_update(int x, int ql, int qr, int id, int l, int r)
{
if(r < ql || qr < l)
return;
if((l <= ql) && (r <= qr) && (x < smn[id]))
{
if(x <= mn[id])
return;
mn[id] = max(mn[id], x);
mnlazy[id] = max(mnlazy[id], x);
return;
}
mx_push(id);
int m = (l+r)/2;
mx_update(x, ql, qr, 2*id, l, m);
mx_update(x, ql, qr, 2*id+1, m+1, r);
fix(id);
return;
}
void mn_update(int x, int ql, int qr, int id, int l, int r)
{
if(r < ql || qr < l)
return;
if((l <= ql) && (r <= qr) && (x < smx[id]))
{
if(x <= mx[id])
return;
mx[id] = max(mx[id], x);
mxlazy[id] = max(mxlazy[id], x);
return;
}
mn_push(id);
int m = (l+r)/2;
mn_update(x, ql, qr, 2*id, l, m);
mn_update(x, ql, qr, 2*id+1, m+1, r);
fix(id);
return;
}
int val(int pos, int id, int l, int r)
{
if(l==r)
return mx[id];
mn_push(id);
mx_push(id);
int m = (l+r)/2;
if(pos <= m)
return val(pos, 2*id, l, m);
else
return val(pos, 2*id+1, m+1, r);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
mx_mn_iser_segment_tree work;
work.init();
for(int i = 0; i < k; i++)
{
if(op[i] == 1)
work.mx_update(height[i], left[i], right[i], 1, 0, n);
else
work.mn_update(height[i], left[i], right[i], 1, 0, n);
}
for(int i = 0; i < n; i++)
finalHeight[i] = work.val(i, 1, 0, n);
return;
}