| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 938061 | RadicaI | 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>
#define int long long
#define pi pair<int,int>
#define pb push_back
#define V vector
#define vi V<int>
#define mi map<int,int>
#define MOD 1000000007
#define MOD2 998244353
#define mp make_pair
#define ins insert
#define qi queue<int>
#define pqi priority_queue<int>
#define si set<int>
#define v2i V<vi>
#define v3i V<v2i>
#define v4i V<v3i>
#define v5i V<v4i>
#define INF 1e18
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl "\n"
#define ub upper_bound
#define print(x) cout << x<<" ";
#define vpi V<pi>
#define Y cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define msi multiset<int>
#define F first
#define S second
#define ld long double
#define RE return;
#define IMP cout<<-1<<endl;return;
using namespace std;
template <typename T>
std::istream& operator>>(std::istream& in, std::vector<T>& vec) {
for (T& x : vec) {
in >> x;
}
return in;
}
struct Node{
int mx; int mn;
int val;
int l,r;
};
V<Node> arr;
vi loc;
void build(int node, int l, int r){
arr[node].val=0; arr[node].mn = INF; arr[node].mx=-INF;
arr[node].l =l; arr[node].r = r;
if(l==r){
loc[l] = node;
return;
}
int mid = (l+r)/2;
build(2*node, l, mid); build(2*node+1, mid+1, r);
}
void push(int node){
if(arr[node].mx != -INF){
arr[2*node].mn = INF;
arr[2*node].mx = max(arr[2*node].mx, arr[node].mx);
arr[2*node].val = max(arr[2*node].val, arr[node].mx);
arr[2*node+1].mn = INF;
arr[2*node+1].mx = max(arr[2*node+1].mx, arr[node].mx);
arr[2*node+1].val = max(arr[2*node+1].val, arr[node].mx);
arr[node].mx =-INF;
}else if(arr[node].mn != INF){
arr[2*node].mx = -INF;
arr[2*node].mn = min(arr[2*node].mn, arr[node].mn);
arr[2*node].val = min(arr[2*node].val, arr[node].mn);
arr[2*node+1].mx = -INF;
arr[2*node+1].mn = min(arr[2*node+1].mn, arr[node].mn);
arr[2*node+1].val = min(arr[2*node+1].val, arr[node].mn);
arr[node].mn =INF;
}
}
void update(int node, int l, int r, int tl, int tr, int typ, int val){
//cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<endl;
if(tl>tr) return;
if(l==tl && r==tr){
if(typ==1){
arr[node].mn = INF;
arr[node].mx =max(arr[node].mx, val);
arr[node].val = max(arr[node].val, val);
}else{
arr[node].mx = -INF;
arr[node].mn =min(arr[node].mn, val);
arr[node].val = min(arr[node].val, val);
}
return;
}
push(node);
int mid = (l+r)/2;
update(2*node, l, mid, tl, min(mid, tr), typ, val);
update(2*node+1, mid+1, r, max(tl, mid+1), tr, typ, val);
}
int query(int node, int l, int r, int i){
if(l==r){
return arr[node].val;
}
push(node);
int mid = (l+r)/2;
if(i<=mid) return query(2*node, l, mid, i);
else return query(2*node+1, mid+1, r, i);
}
void buildWall(int n, int k, int *op, int *left, int *right, int *height, int *finalHeight){
arr.resize(4*n); loc.resize(n);
for(int i=1; i<4*n; i++)arr[i].r=0;
build(1, 0, n-1);
for(int i=0; i<k; i++){
update(1, 0, n-1, left[i], right[i], op[i], height[i]);
}
for(int i=0; i<n; i++) finalHeight[i] = query(1, 0, n-1,i);
}
int n, q, op[500005], lb[500005], rb[500005], h[500005], ans[500005];
signed main() {
cin >> n >> q;
for (int i = 0; i < q; i++)
cin >> op[i] >> lb[i] >> rb[i] >> h[i];
buildWall(n, q, op, lb, rb, h, ans);
for (int i = 0; i < n; i++)
cout << ans[i] << ' ';
cout << '\n';
}