| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 727046 | Narka | 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>
using namespace std ;
# define F first
# define S second
# define int long long
# define in insert
# define pb push_back
# define pob pop_back
# define INF INT_MAX
# define INFL 1e18 + 10
# define mod 1000000007
# define vi vector<int>
# define pii pair<int , int>
# define vvi vector< vector<int> >
# define vpi vector<pair<int, int>>
# define all(v) v.begin() , v.end()
# define debug(x) cerr << '\n' << #x << " = " << x << '\n' ;
# define rep( i , s , e ) for( int i = s ; i <= e ; i++ )
# define repR( i , e , s ) for( int i = e ; i >= s ; i-- )
# define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
# define endl "\n"
struct id {
int mn = INF, mx = 0;
};
vector<id> add;
vector<bool> check, check1;
id clear;
void build(int n) {
add.resize(n*4, clear);
check.resize(n*4, false);
check1.resize(n*4, false);
}
void pro(int x, int l, int r) {
if (r - l == 1) return;
if (!check[x] && !check1[x]) return;
if (check[x]) {
add[x*2+1].mn = min(add[x].mn, add[x*2+1].mn);
add[x*2+1].mx = max(add[x].mx, add[x*2+1].mx);
add[x*2+1].mx = min(add[x*2+1].mn, add[x*2+1].mx);
check[x*2+1] = true; check1[x*2+1] = false;
add[x*2+2].mn = min(add[x].mn, add[x*2+2].mn);
add[x*2+2].mx = max(add[x].mx, add[x*2+2].mx);
add[x*2+2].mx = min(add[x*2+2].mn, add[x*2+2].mx);
check[x*2+2] = true; check1[x*2+2] = false;
check[x] = false;
} else {
add[x*2+2].mx = max(add[x*2+2].mx, add[x].mx);
add[x*2+2].mn = min(add[x*2+2].mn, add[x].mn);
add[x*2+2].mn = max(add[x*2+2].mx, add[x*2+2].mn);
check1[x*2+2] = true; check[x*2+2] = false;
add[x*2+1].mx = max(add[x*2+1].mx, add[x].mx);
add[x*2+1].mn = min(add[x*2+1].mn, add[x].mn);
add[x*2+1].mn = max(add[x*2+1].mx, add[x*2+1].mn);
check1[x*2+1] = true; check[x*2+1] = false;
check1[x] = false;
}
add[x].mn = INF; add[x].mx = 0;
}
void build(int lx, int rx, int mx, int mn, int x, int l, int r) {
pro(x, l, r);
if (lx == l && rx == r) {
//cout << add[x].mn << " " << add[x].mx << " " << l << " " << r << endl;
if (mx == -1) {
add[x].mn = min(add[x].mn, mn);
add[x].mx = min(add[x].mn, add[x].mx);
check[x] = true; check1[x] = false;
} else {
add[x].mx = max(add[x].mx, mx);
add[x].mn = max(add[x].mx, add[x].mn);
check1[x] = true; check[x] = false;
}
return;
}
int md = (l + r) >> 1;
if (md >= rx) {
build(lx, rx, mx, mn, x*2+1, l, md);
} else if (md <= lx) {
build(lx, rx, mx, mn, x*2+2, md, r);
} else {
build(lx, md, mx, mn, x*2+1, l, md);
build(md, rx, mx, mn, x*2+2, md, r);
}
}
void search(int i, int x, int l, int r){
pro(x, l, r);
if (r - l == 1) {
cout << min(add[x].mn, add[x].mx) << endl;
return;
}
int md = (l + r) >> 1;
if (i < md) search(i, x*2+1, l, md);
else search(i, x*2+2, md, r);
}
void solve() {
int n, m;
cin >> n >> m;
build(n);
while(m--) {
int x, l, r, v;
cin >> x >> l >> r >> v;
if (x == 1) build(l, r+1, v, INF, 0, 0, n);
else build(l, r+1, -1, v, 0, 0, n);
}
rep(i, 0, n-1) {
search(i, 0, 0, n);
}
cout << endl;
}
int32_t main() {
// FAST
solve();
return 0;
}