oj.uz

Submission #395145

# Submission time Handle Problem Language Result Execution time Memory
395145 2021-04-27T21:54:21 Z jeroenodb Wall (IOI14_wall) C++14
100 / 100
 761 ms 92100 KB 
#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
int* pt;
struct segtree {
    int n, ptwo;
    struct Node {
        // Change here the values you want to propagate, and store
        int mn =0, mx = 100000;
        int l,r;
        Node () {}
        Node(int i) {
            l = r = i;
        }
    };
    vector<Node> d;
    void set(int i, int mn, int mx) {
        Node& rc = d[i];
        rc.mn = max(mn,rc.mn);
        rc.mx = min(mx,rc.mx);
        if(rc.mn>rc.mx) {
            if(mn>rc.mx) rc.mx = rc.mn;
            else rc.mn = rc.mx;
        }
    }
    void push(int i) {
        // Pushes the propagation values down to the children
        set(2*i, d[i].mn, d[i].mx);
        set(2*i+1, d[i].mn, d[i].mx);
        d[i].mn = 0; d[i].mx = 100000;
    }
    segtree(int _n) {
        n = _n;
        ptwo= 1;
        while(ptwo<n) ptwo*=2;
        d.resize(2*ptwo);
        for(int i=ptwo;i<ptwo*2;++i) {
            d[i] = Node(i-ptwo);
        }
        for(int i=ptwo-1;i>0;--i) {
            d[i].l = d[i*2].l; d[i].r = d[i*2+1].r;
        }
    }
    void query(int i=1, int mn = 0, int mx = 100000) {
        Node& c = d[i];
        if(c.l>=n) return;
        mn = max(mn,c.mn);
        mx = min(mx,c.mx);
        if(mn>mx) {
            if(c.mn>mx) mn = mx;
            else mx = mn;
        }
        if(c.l==c.r) {
            *pt = mn;
            pt++;
            return;
        }
        query(i*2,mn,mx);
        query(i*2+1,mn,mx);
    }
    void update(int l, int r, bool lower, int val, int i=1) {
        Node& c = d[i];
        if(c.l < l or r < c.r ) {
            push(i);
            int mid = (c.r+c.l)/2;
            if(l<=mid) {
                update(l,r,lower,val,i*2);
            }
            if(r>mid) {
                update(l,r,lower,val,i*2+1);
            }
        } else {
            if(!lower) {
                c.mn = max(val,c.mn);
                if(c.mn>c.mx) c.mx = c.mn;
            } else {
                c.mx = min(val,c.mx);
                if(c.mn>c.mx) c.mn = c.mx;
            }
        }
    }

};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    segtree seg(n);
    pt = finalHeight;
    for(int i=0;i<k;++i) {
        seg.update(left[i],right[i], op[i]==2, height[i]);
    }
    seg.query();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 972 KB Output is correct
5 Correct 7 ms 972 KB Output is correct
6 Correct 5 ms 972 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 159 ms 13892 KB Output is correct
3 Correct 170 ms 8412 KB Output is correct
4 Correct 487 ms 22168 KB Output is correct
5 Correct 306 ms 22796 KB Output is correct
6 Correct 292 ms 21108 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 972 KB Output is correct
5 Correct 5 ms 972 KB Output is correct
6 Correct 6 ms 972 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 167 ms 13900 KB Output is correct
9 Correct 172 ms 8408 KB Output is correct
10 Correct 486 ms 22316 KB Output is correct
11 Correct 296 ms 22724 KB Output is correct
12 Correct 294 ms 21332 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 166 ms 13892 KB Output is correct
15 Correct 37 ms 2428 KB Output is correct
16 Correct 657 ms 22200 KB Output is correct
17 Correct 305 ms 21640 KB Output is correct
18 Correct 308 ms 21652 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 972 KB Output is correct
5 Correct 6 ms 972 KB Output is correct
6 Correct 5 ms 972 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 162 ms 13852 KB Output is correct
9 Correct 173 ms 8464 KB Output is correct
10 Correct 485 ms 22184 KB Output is correct
11 Correct 309 ms 22868 KB Output is correct
12 Correct 293 ms 21180 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 165 ms 13944 KB Output is correct
15 Correct 37 ms 2336 KB Output is correct
16 Correct 642 ms 22268 KB Output is correct
17 Correct 315 ms 21700 KB Output is correct
18 Correct 310 ms 21576 KB Output is correct
19 Correct 757 ms 92076 KB Output is correct
20 Correct 758 ms 91972 KB Output is correct
21 Correct 756 ms 92100 KB Output is correct
22 Correct 752 ms 92036 KB Output is correct
23 Correct 750 ms 91972 KB Output is correct
24 Correct 743 ms 92100 KB Output is correct
25 Correct 744 ms 91968 KB Output is correct
26 Correct 753 ms 91972 KB Output is correct
27 Correct 757 ms 92032 KB Output is correct
28 Correct 749 ms 92032 KB Output is correct
29 Correct 755 ms 92016 KB Output is correct
30 Correct 761 ms 92032 KB Output is correct