oj.uz

Submission #672440

# Submission time Handle Problem Language Result Execution time Memory
672440 2022-12-16T07:31:12 Z bLIC Wall (IOI14_wall) C++17
100 / 100
 662 ms 135220 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 1268 KB Output is correct
5 Correct 4 ms 1364 KB Output is correct
6 Correct 5 ms 1364 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 117 ms 8056 KB Output is correct
3 Correct 150 ms 9136 KB Output is correct
4 Correct 443 ms 24632 KB Output is correct
5 Correct 281 ms 25540 KB Output is correct
6 Correct 259 ms 23864 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 4 ms 1364 KB Output is correct
6 Correct 5 ms 1364 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 122 ms 13860 KB Output is correct
9 Correct 141 ms 9036 KB Output is correct
10 Correct 430 ms 24676 KB Output is correct
11 Correct 269 ms 25412 KB Output is correct
12 Correct 263 ms 23852 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 125 ms 13860 KB Output is correct
15 Correct 24 ms 3020 KB Output is correct
16 Correct 406 ms 24652 KB Output is correct
17 Correct 268 ms 24100 KB Output is correct
18 Correct 260 ms 24048 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 5 ms 1364 KB Output is correct
6 Correct 4 ms 1340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 121 ms 13924 KB Output is correct
9 Correct 143 ms 8996 KB Output is correct
10 Correct 437 ms 24692 KB Output is correct
11 Correct 270 ms 25412 KB Output is correct
12 Correct 266 ms 23860 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 129 ms 13812 KB Output is correct
15 Correct 24 ms 3096 KB Output is correct
16 Correct 404 ms 24688 KB Output is correct
17 Correct 263 ms 24132 KB Output is correct
18 Correct 265 ms 24128 KB Output is correct
19 Correct 636 ms 135152 KB Output is correct
20 Correct 643 ms 132732 KB Output is correct
21 Correct 641 ms 135220 KB Output is correct
22 Correct 630 ms 132764 KB Output is correct
23 Correct 634 ms 132684 KB Output is correct
24 Correct 630 ms 132732 KB Output is correct
25 Correct 646 ms 132648 KB Output is correct
26 Correct 650 ms 135148 KB Output is correct
27 Correct 640 ms 135156 KB Output is correct
28 Correct 662 ms 132648 KB Output is correct
29 Correct 643 ms 132708 KB Output is correct
30 Correct 641 ms 132672 KB Output is correct