Submission #672440

#	Time	Username	Problem	Language	Result	Execution time	Memory
672440		bLIC	Wall (IOI14_wall)	C++17	100 / 100	662 ms	135220 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(INF), mn(0){}
    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 opt(Node& par, Node& chi){
    chi.mx = min(chi.mx, par.mx);
    chi.mx = max(chi.mx, par.mn);
    chi.mn = max(chi.mn, par.mn);
    chi.mn = min(chi.mn, par.mx);
}

void pushdown(int x){
    if (x>=n) return;
    opt(tree[x], tree[lt(x)]);
    opt(tree[x], tree[rt(x)]);
    tree[x].mn = 0;
    tree[x].mx = INF;
}

// 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) {
        tree[x].mx = min(tree[x].mx, val);
        tree[x].mn = min(tree[x].mn, val);
        return;
    }
    if (l>=rx || r<=lx) return;
    int m = (lx+rx)/2;
    pushdown(x);
    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) {
        tree[x].mx = max(tree[x].mx, val);
        tree[x].mn = max(tree[x].mn, val);
        return;
    }
    if (l>=rx || r<=lx) return;
    int m = (lx+rx)/2;
    pushdown(x);
    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]+1, height[i]);
        else updatemx(left[i], right[i]+1, height[i]);
    }
    for (int i = 1;i<::n;i++) pushdown(i);
    for (int i = 0;i<n;i++) finalHeight[i] = min(tree[i+::n].mn, tree[i+::n].mx);
}


// 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
// }
// int main()
// {
//   int n;
//   int k;

//   int i, j;  
//   int status = 0;

//   status = scanf("%d%d", &n, &k);
//   assert(status == 2);

//   int* op = (int*)calloc(sizeof(int), k);
//   int* left = (int*)calloc(sizeof(int), k);
//   int* right = (int*)calloc(sizeof(int), k);
//   int* height = (int*)calloc(sizeof(int), k);
//   int* finalHeight = (int*)calloc(sizeof(int), n);

//   for (i = 0; i < k; i++){
//     status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
//     assert(status == 4);
//   }

//   buildWall(n, k, op, left, right, height, finalHeight);

//   for (j = 0; j < n; j++)
//     printf("%d\n", finalHeight[j]);
  
//   return 0;
// }	

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