| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 672376 | bLIC | 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 <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
// typedef tree<int,null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define ft first
#define sd second
#define pb push_back
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vl> vvl;
#define dbg if(0)
const ll MOD = 998244353;
const ll INFLL = 1e18;
const int INF = 1e9;
const int maxN = 2e5+6;
const int maxK = 10;
void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}
#define gbit(x, i) (((1<<i)&(x))!=0)
template <typename T>
class MINT{
T x;
public:
static T MOD;
MINT(T _x){x = (_x%MOD+MOD)%MOD;}
MINT():MINT(0){}
explicit operator ll(){return x;}
friend MINT operator+(const MINT& m1, const MINT& m2){return MINT((m1.x + m2.x)%MOD);};
friend MINT operator-(const MINT& m1, const MINT& m2){return MINT(((m1.x - m2.x)%MOD + MOD)%MOD);};
friend MINT operator*(const MINT& m1, const MINT& m2){return MINT((m1.x * m2.x)%MOD);};
MINT& operator+=(const MINT& m2){return *this = *this + m2;};
MINT& operator-=(const MINT& m2){return *this = *this - m2;};
MINT& operator*=(const MINT& m2){return *this = *this * m2;};
friend bool operator==(const MINT& m1, const MINT& m2){return m1.x==m2.x;};
friend istream& operator>>(istream& in, const MINT& m){in>>m.x;return in;};
friend ostream& operator<<(ostream& out, const MINT& m){out<<m.x;return out;};
};
template <typename T>
T MINT<T>::MOD = 998244353;
typedef MINT<ll> mll;
typedef pair<mll, mll> pmll;
#define lt(x) ((x)<<1)
#define rt(x) ((x)<<1|1)
struct Node {
ll h, mx, mn;
Node(ll x):h(x), mx(-1), mn(-1){}
Node():Node(0){}
};
vector<Node> tree;
int n;
void init(int _n){
n = 1;
while(n<_n) n<<=1;
tree.assign(2*n, Node());
}
void pushdown(int x, int lx, int mid, int rx){
if (x>=n) return;
if (tree[x].mx!=-1){
tree[lt(x)].h = min(tree[lt(x)].h, tree[x].mx);
tree[rt(x)].h = min(tree[rt(x)].h, tree[x].mx);
}else if (tree[x].mn!=-1){
tree[lt(x)].h = max(tree[lt(x)].h, tree[x].mn);
tree[rt(x)].h = max(tree[rt(x)].h, tree[x].mn);
}
tree[x].mn = tree[x].mx = -1;
}
void build(vector<ll>& v){
for (int i = 0;i<sz(v);i++) tree[i+n] = v[i];
for (int i = n-1;i>0;i--) pushup(i);
}
void updatemx(int l, int r, int x, int lx, int rx, ll val){
if (l<=lx && rx<=r) {
pushdown(x);
tree[x].h = min(tree[x].h, val);
tree[x].mx = val;
return;
}
if (l>=rx || r<=lx) return;
int m = (lx+rx)/2;
pushdown(x, lx, m, rx);
updatemx(l, r, lt(x), lx, m, val);
updatemx(l, r, rt(x), m, rx, val);
pushup(x);
}
void updatemx(int l, int r, ll val){
updatemx(l, r, 1, 0, n, val);
}
void updatemn(int l, int r, int x, int lx, int rx, ll val){
if (l<=lx && rx<=r) {
pushdown(x);
tree[x].h = max(tree[x].h, val);
tree[x].mx = val;
return;
}
if (l>=rx || r<=lx) return;
int m = (lx+rx)/2;
pushdown(x, lx, m, rx);
updatemn(l, r, lt(x), lx, m, val);
updatemn(l, r, rt(x), m, rx, val);
pushup(x);
}
void updatemn(int l, int r, ll val){
updatemn(l, r, 1, 0, n, val);
}
// ll querysm(int l, int r, int x, int lx, int rx){
// if (l<=lx && rx<=r) return tree[x].s;
// else if (l>=rx || r<=lx) return 0;
// else {
// int m = (lx+rx)/2;
// pushdown(x, lx, m, rx);
// return (querysm(l, r, lt(x), lx, m)+querysm(l,r , rt(x), m, rx));
// }
// }
// ll querysm(int l, int r){
// return querysm(l, r, 1, 0, n);
// }
// ll querymin(int l, int r, int x, int lx, int rx){
// if (l<=lx && rx<=r) return tree[x].m;
// else if (l>=rx || r<=lx) return -INFLL;
// else {
// int m = (lx+rx)/2;
// pushdown(x, lx, m, rx);
// return max(querymin(l, r, lt(x), lx, m), querymin(l, r, rt(x), m, rx));
// }
// }
// ll querymin(int l, int r){
// return querymin(l, r, 1, 0, n);
// }
template <class T>
istream& operator>>(istream& in, vector<T>& v){
for (T& x:v) in>>x;
return in;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
init(n);
vi h(n);
// for (int i = 0;i<n;i++) h[i] = height[i];
build(h);
for (int i = 0;i<k;i++){
if (op[i]==1) updatemn(left[i], right[i], height[i]);
else updatemx(left[i], right[i], height[i]);
}
for (int i = 0;i<n;i++) finalHeight[i] = tree[i+::n].h;
}
// void solve(){
// }
// int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
// cout.tie(nullptr);
// // #define _DEBUG
// #ifdef _DEBUG
// freopen("haybales.in", "r", stdin);
// freopen("haybales.out", "w", stdout);
// int tt = clock();
// #endif
// int t=1, i = 1;
// // cin>>t;
// while(t--){
// // cout<<"Case #"<<i++<<": ";
// solve();
// // cout<<'\n';
// }
// #ifdef _DEBUG
// cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl;
// tt = clock();
// #endif
// }