oj.uz

Submission #585430

# Submission time Handle Problem Language Result Execution time Memory
585430 2022-06-28T23:10:03 Z erto Wall (IOI14_wall) C++17
100 / 100
 612 ms 59228 KB 
#include <bits/stdc++.h>
typedef long long int ll;
#define INF ll(1e9 + 7)
#define INF2 998244353
#define N (ll)(1e5 + 5)
using namespace std;
//#define int ll
#define lsb(x) (x & (-x))
 
int n, g, h,m,  q,z,t1,t2, ans=0, ans2, n2, k, n3; 

int comb(int x, int y){
    return max(x, y);
}
 
struct SegTree{
    int n;
    vector<int> tmax, tmin;
 
    SegTree(int _n){
        n = _n+1;
        while(lsb(n) != n)
            n += lsb(n);
        tmax.resize(2*n, 0);
        tmin.resize(2*n, INF);
    }
 

    void push(int i, int len){
        if(!len)return;
        if(tmin[i] != INF){
            tmin[i * 2 + 1] = min(tmin[i * 2 + 1], tmin[i]);
            tmax[i * 2 + 1] = min(tmin[i * 2 + 1], tmax[i * 2 + 1]);
            tmin[i * 2] = min(tmin[i * 2], tmin[i]);
            tmax[i * 2] = min(tmin[i * 2], tmax[i * 2]);
            tmin[i] = INF;
        }
        if(tmax[i]){
            tmax[i * 2 + 1] = max(tmax[i * 2 + 1], tmax[i]);
            tmin[i * 2 + 1] = max(tmin[i * 2 + 1], tmax[i * 2 + 1]);
            tmax[i * 2] = max(tmax[i * 2], tmax[i]);
            tmin[i * 2] = max(tmin[i * 2], tmax[i * 2]);
            tmax[i] = 0;
        }
    }

    void maxx(int v, int ql, int qr){maxx(1, v, 0, n - 1, ql, qr);}
    void maxx(int i, int v, int lb, int rb, int ql, int qr){
        if(lb > qr || rb < ql)return;
        if(ql <= lb && rb <= qr){
            tmax[i] = max(tmax[i], v);
            tmin[i] = max(tmin[i], tmax[i]);
            return;
        }
        int md = (rb + lb) /2;
        push(i, (rb - lb + 1) / 2);

        maxx(i * 2, v, lb, md, ql, qr);
        maxx(i * 2 + 1, v, md + 1, rb, ql, qr);
        //tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
    }   

    void minn(int v, int ql, int qr){minn(1, v, 0, n - 1, ql, qr);}
    void minn(int i, int v, int lb, int rb, int ql, int qr){
        if(lb > qr || rb < ql)return;
        if(ql <= lb && rb <= qr){
            tmin[i] = min(tmin[i], v);
            tmax[i] = min(tmax[i], tmin[i]);
            return;
        }
        int md = (rb + lb) /2;
        push(i, (rb - lb + 1) / 2);

        minn(i * 2, v, lb, md, ql, qr);
        minn(i * 2 + 1, v, md + 1, rb, ql, qr);
        //tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
    }   

    int qu(int i){
        int t1=0;
        i+=n;
        while(i){
            t1 = min(t1, tmin[i]);
            t1 = max(t1, tmax[i]);
            i /= 2;
        }
        return t1;
    }
};  

void buildWall(int n, int k, int op[], int le[], int ri[], int height[], int finalHeight[]){
    SegTree s(n + 1);
    for(int i=0; i<k; i++){
        if(op[i] == 1){
            s.maxx(height[i], le[i], ri[i]);
        }
        else{
            s.minn(height[i], le[i], ri[i]);
        }
    }

    for(int i=0; i<n; i++){
        finalHeight[i] = s.qu(i);
    }
    return;
}

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 212 KB Output is correct
4 Correct 6 ms 692 KB Output is correct
5 Correct 5 ms 756 KB Output is correct
6 Correct 4 ms 724 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 140 ms 8080 KB Output is correct
3 Correct 133 ms 4128 KB Output is correct
4 Correct 353 ms 10576 KB Output is correct
5 Correct 226 ms 10572 KB Output is correct
6 Correct 259 ms 10580 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 3 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 6 ms 772 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 141 ms 13920 KB Output is correct
9 Correct 143 ms 7904 KB Output is correct
10 Correct 368 ms 20156 KB Output is correct
11 Correct 258 ms 20604 KB Output is correct
12 Correct 229 ms 19120 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 140 ms 14040 KB Output is correct
15 Correct 25 ms 1904 KB Output is correct
16 Correct 443 ms 20184 KB Output is correct
17 Correct 215 ms 19552 KB Output is correct
18 Correct 220 ms 19604 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 212 KB Output is correct
4 Correct 7 ms 724 KB Output is correct
5 Correct 4 ms 776 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 133 ms 13924 KB Output is correct
9 Correct 136 ms 7876 KB Output is correct
10 Correct 421 ms 20180 KB Output is correct
11 Correct 216 ms 20696 KB Output is correct
12 Correct 208 ms 19172 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 144 ms 13900 KB Output is correct
15 Correct 34 ms 1884 KB Output is correct
16 Correct 419 ms 20184 KB Output is correct
17 Correct 260 ms 19708 KB Output is correct
18 Correct 218 ms 19600 KB Output is correct
19 Correct 603 ms 59200 KB Output is correct
20 Correct 612 ms 59212 KB Output is correct
21 Correct 601 ms 59184 KB Output is correct
22 Correct 556 ms 59228 KB Output is correct
23 Correct 554 ms 59172 KB Output is correct
24 Correct 566 ms 59208 KB Output is correct
25 Correct 581 ms 59216 KB Output is correct
26 Correct 590 ms 59220 KB Output is correct
27 Correct 576 ms 59212 KB Output is correct
28 Correct 597 ms 59152 KB Output is correct
29 Correct 580 ms 59148 KB Output is correct
30 Correct 564 ms 59196 KB Output is correct