oj.uz

Submission #291136

# Submission time Handle Problem Language Result Execution time Memory
291136 2020-09-04T18:20:34 Z ivan24 Wall (IOI14_wall) C++14
100 / 100
 1452 ms 132672 KB 
#include "wall.h"

#include <bits/stdc++.h>
using namespace std;
using ll = int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second

const ll INF = 1e9;

class SegmentTree {
private:
    vi st, data;
    vii lzy;
    ll n;
    ll left(ll x){ return (x << 1); }
    ll right(ll x) { return ((x << 1) + 1); }
    ii cmbNodes(ii lhs, ii rhs){
        ii ans = ii(max(lhs.F,rhs.F),min(lhs.S,rhs.S));
        if (ans.F <= ans.S) return ans;
        if (lhs.S < rhs.F) ans.F = lhs.S;
        else ans.S = lhs.F;
        return ans;
    }
    void rangeUpdate (ll i, ll l, ll r, ll ul, ll ur, ii newNode){
        //cout << i << " " << l << " " << r << " " << ul << " " << ur << " " << endl;
        if (l != r){
            lzy[left(i)] = cmbNodes(lzy[i],lzy[left(i)]);
            lzy[right(i)] = cmbNodes(lzy[i],lzy[right(i)]);
            lzy[i] = ii(0,INF);
        }
        if (ur >= r && l >= ul){
            lzy[i] = cmbNodes(newNode,lzy[i]);
        }else if (max(ul,l) <= min(ur,r)){
            ll m = (l+r)/2;
            rangeUpdate(left(i),l,m,ul,ur,newNode);
            rangeUpdate(right(i),m+1,r,ul,ur,newNode);
        }
    }
    ii query (ll i, ll l, ll r, ll idx){
        if (r >= idx && idx >= l){
            ii ans = lzy[i];
            ll m = (l+r)/2;
            if (l != r){
                ii lans = query(left(i),l,m,idx);
                ii rans = query(right(i),m+1,r,idx);
                ans = cmbNodes(ans,lans);
                ans = cmbNodes(ans,rans);
            }
            return ans;
        }else{
            return ii(0,INF);
        }
    }
    void printLzy(ll i, ll l, ll r){
        cout << i << "  " << l << "-" << r << " : " << lzy[i].F << " , " << lzy[i].S << endl;
        if (l != r){
            ll m = (l+r)/2;
            printLzy(left(i),l,m);
            printLzy(right(i),m+1,r);
        }
    }
    void build (ll i, ll l, ll r){
        if (l == r){
            lzy[i] = ii(0,0);
        }else{
            lzy[i] = ii(0,INF);
            ll m = (l+r)/2;
            build(left(i),l,m);
            build(right(i),m+1,r);
        }
    }
public:
    SegmentTree (ll sz): st(sz*4), data(sz), lzy(sz*4,ii(0,0)), n(sz){
        build(1,0,n-1);
    }
    void update (ll l, ll r, ii newNode){
        rangeUpdate(1,0,n-1,l,r,newNode);
    }
    ll query (ll idx){
        ii ans = query(1,0,n-1,idx);
        //cout << ans.F << " " << ans.S << endl;
        return ans.F;
    }
    vi get_all_data(){
        vi ans(n);
        for (ll i = 0; n > i; i++) ans[i] = query(i);
        return ans;
    }
    void print(){
        printLzy(1,0,n-1);
    }
    void print_data(){
        vi res = get_all_data();
        for (auto i: res) cout << i << " ";
        cout << endl;
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SegmentTree st(n);
    for (ll i = 0; k > i; i++){
        //cout << i << endl;
        ii newNode = ii(0,INF);
        if (op[i] == 1) newNode.F = height[i];
        else newNode.S = height[i];
        st.update(left[i],right[i],newNode);
        //st.print_data();
        //st.print();
    }
    //st.print();
    vi res = st.get_all_data();
    for (ll i = 0; n > i; i++) finalHeight[i] = abs(res[i]);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 10 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 173 ms 8312 KB Output is correct
3 Correct 207 ms 4600 KB Output is correct
4 Correct 598 ms 14200 KB Output is correct
5 Correct 393 ms 16632 KB Output is correct
6 Correct 377 ms 16760 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 10 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 178 ms 8184 KB Output is correct
9 Correct 213 ms 4728 KB Output is correct
10 Correct 606 ms 14076 KB Output is correct
11 Correct 393 ms 18168 KB Output is correct
12 Correct 377 ms 16632 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 186 ms 9336 KB Output is correct
15 Correct 47 ms 2424 KB Output is correct
16 Correct 813 ms 17784 KB Output is correct
17 Correct 397 ms 17144 KB Output is correct
18 Correct 394 ms 17108 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 416 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 10 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 173 ms 8184 KB Output is correct
9 Correct 212 ms 4604 KB Output is correct
10 Correct 605 ms 14072 KB Output is correct
11 Correct 396 ms 18248 KB Output is correct
12 Correct 391 ms 16632 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 178 ms 9256 KB Output is correct
15 Correct 47 ms 2424 KB Output is correct
16 Correct 806 ms 17572 KB Output is correct
17 Correct 418 ms 17156 KB Output is correct
18 Correct 394 ms 17144 KB Output is correct
19 Correct 1415 ms 130168 KB Output is correct
20 Correct 1404 ms 132672 KB Output is correct
21 Correct 1415 ms 132572 KB Output is correct
22 Correct 1416 ms 132472 KB Output is correct
23 Correct 1452 ms 132584 KB Output is correct
24 Correct 1403 ms 132472 KB Output is correct
25 Correct 1439 ms 132344 KB Output is correct
26 Correct 1426 ms 132088 KB Output is correct
27 Correct 1441 ms 132088 KB Output is correct
28 Correct 1393 ms 132088 KB Output is correct
29 Correct 1406 ms 132088 KB Output is correct
30 Correct 1410 ms 132108 KB Output is correct