Submission #672379

#	Time	Username	Problem	Language	Result	Execution time	Memory
672379		bLIC	Wall (IOI14_wall)	C++17	0 / 100	1 ms	212 KiB

wall

#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, lx, (lx+rx)/2, rx);
        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, lx, (lx+rx)/2, rx);
        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
// }

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39