oj.uz

Submission #276933

# Submission time Handle Problem Language Result Execution time Memory
276933 2020-08-20T19:49:38 Z Dremix10 Wall (IOI14_wall) C++17
100 / 100
 913 ms 151800 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
    #define p(x)
    #define p2(x,y)
    #define pp(x)
    #define pv(x)
    #define ppv(x)
#endif
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 1e18;
const int MOD = 1e9+7;
const int N = 2e5+1;

template<typename T>
struct SEGTREE{
    struct node{
        T val; // for adding more stuff
        T mini,maxi,rep;

        node() : val(0), mini(-1), maxi(-1), rep(-1) {}
        node(T _val) : val(_val), mini(-1), maxi(-1), rep(-1) {}
    };
    vector<node> seg;
    int N;

    void init(int n){
        N = n;
        seg.assign(4*n,node());
    }

    node merge(node x, node y){
        node res;
        return res;
    }

    void look(node x){
        cout<<x.val<<" "<<x.mini<<" "<<x.maxi<<" "<<x.rep<<endl;
    }

    void add(node &x, int val){
        /// if both then max<min
        if(x.rep!=-1){
            x.rep = max(x.rep,val);
            x.val = x.rep;
            return;
        }
        x.maxi = max(x.maxi,val);
        if(x.mini !=-1 && x.mini <= x.maxi){
            x.rep = x.maxi;
            x.mini = -1;
            x.maxi = -1;
            x.val = x.rep;
        }
        else{
            x.val = max(x.val,x.maxi);
            if(x.mini!=-1)
                x.val = min(x.val,x.mini);
        }
    }

    void rem(node &x, int val){
        /// if both then max < min
        if(x.rep!=-1){
            x.rep = min(x.rep,val);
            x.val = x.rep;
            return;
        }
        if(x.mini == -1)x.mini = val;
        else x.mini = min(x.mini,val);
        if(x.mini <= x.maxi){
            x.rep = x.mini;
            x.mini = -1;
            x.maxi = -1;
            x.val = x.rep;
        }
        else{
            x.val = max(x.val,x.maxi);
            x.val = min(x.val,x.mini);
        }
    }

    void push(node &par, node &x, node &y, int r1, int r2){
        if(par.rep!=-1){
            x.val = par.rep;
            x.rep = par.rep;
            x.mini = -1;
            x.maxi = -1;
            y.val = par.rep;
            y.rep = par.rep;
            y.mini = -1;
            y.maxi = -1;
            par.rep = -1;
            return;
        }
        if(par.maxi!=-1){
            add(x,par.maxi);
            add(y,par.maxi);
        }
        if(par.mini!=-1){
            rem(x,par.mini);
            rem(y,par.mini);
        }
        par.maxi = -1;
        par.mini = -1;
    }

    void build(int s, int e, int idx, T arr[]){
        if(s == e){
            seg[idx] = node(arr[s]);
            return;
        }
        int mid = (s+e)/2;
        build(s,mid,idx*2,arr);
        build(mid+1,e,idx*2+1,arr);
        seg[idx] = merge(seg[idx*2],seg[idx*2+1]);
    }

    // supports 1-indexing
    void build(T arr[]){
        build(1,N,1,arr);
    }

    /// add
    void update1(int s, int e, int idx, int qs, int qe, T val){
        //cout<<s<<" "<<e<<endl;
        //look(seg[idx]);
        if(qs<=s && e<=qe){
            add(seg[idx],val);
            //look(seg[idx]);
            return;
        }
        if(s>qe || e<qs)
            return;
        int mid = (s+e)/2;
        push(seg[idx],seg[idx*2],seg[idx*2+1],mid-s+1,e-mid);
        update1(s,mid,idx*2,qs,qe,val);
        update1(mid+1,e,idx*2+1,qs,qe,val);
        seg[idx] = merge(seg[idx*2],seg[idx*2+1]);
    }

    // add to all i (l<=i && i<=r) += val
    void update1(int l, int r, T val){
        update1(1,N,1,l,r,val);
    }

    /// rem
    void update2(int s, int e, int idx, int qs, int qe, T val){
        if(qs<=s && e<=qe){
            rem(seg[idx],val);
            return;
        }
        if(s>qe || e<qs)
            return;
        int mid = (s+e)/2;
        push(seg[idx],seg[idx*2],seg[idx*2+1],mid-s+1,e-mid);
        update2(s,mid,idx*2,qs,qe,val);
        update2(mid+1,e,idx*2+1,qs,qe,val);
        seg[idx] = merge(seg[idx*2],seg[idx*2+1]);
    }

    // add to all i (l<=i && i<=r) += val
    void update2(int l, int r, T val){
        update2(1,N,1,l,r,val);
    }

    void query(int s, int e, int idx, int ans[]){
        if(s==e){
            ans[s-1] = seg[idx].val;
            return;
        }
        int mid = (s+e)/2;
        push(seg[idx],seg[idx*2],seg[idx*2+1],mid-s+1,e-mid);
        query(s,mid,idx*2,ans);
        query(mid+1,e,idx*2+1,ans);
    }

    void query(int ans[]){
        query(1,N,1,ans);
    }

};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SEGTREE<int> seg;
    seg.init(n);

    int i;
    for(i=0;i<k;i++){
        //cout<<op[i]<<" "<<left[i]+1<<" "<<right[i]+1<<" "<<height[i]<<endl;
        if(op[i]==1){
            seg.update1(left[i]+1,right[i]+1,height[i]);
        }
        else
            seg.update2(left[i]+1,right[i]+1,height[i]);
    }

    seg.query(finalHeight);



}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 165 ms 13968 KB Output is correct
3 Correct 221 ms 8696 KB Output is correct
4 Correct 851 ms 24464 KB Output is correct
5 Correct 390 ms 24920 KB Output is correct
6 Correct 373 ms 23416 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 1152 KB Output is correct
5 Correct 6 ms 1152 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 166 ms 13944 KB Output is correct
9 Correct 217 ms 8696 KB Output is correct
10 Correct 756 ms 24536 KB Output is correct
11 Correct 360 ms 25016 KB Output is correct
12 Correct 350 ms 23572 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 172 ms 13944 KB Output is correct
15 Correct 38 ms 2656 KB Output is correct
16 Correct 687 ms 24452 KB Output is correct
17 Correct 371 ms 23808 KB Output is correct
18 Correct 359 ms 23800 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 7 ms 1280 KB Output is correct
5 Correct 6 ms 1152 KB Output is correct
6 Correct 7 ms 1152 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 164 ms 13944 KB Output is correct
9 Correct 215 ms 8572 KB Output is correct
10 Correct 708 ms 24568 KB Output is correct
11 Correct 352 ms 24952 KB Output is correct
12 Correct 367 ms 23544 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 167 ms 13932 KB Output is correct
15 Correct 42 ms 2560 KB Output is correct
16 Correct 705 ms 24488 KB Output is correct
17 Correct 350 ms 23812 KB Output is correct
18 Correct 362 ms 23928 KB Output is correct
19 Correct 887 ms 151724 KB Output is correct
20 Correct 913 ms 151704 KB Output is correct
21 Correct 889 ms 151768 KB Output is correct
22 Correct 874 ms 151672 KB Output is correct
23 Correct 886 ms 151780 KB Output is correct
24 Correct 888 ms 151672 KB Output is correct
25 Correct 874 ms 151768 KB Output is correct
26 Correct 913 ms 151672 KB Output is correct
27 Correct 904 ms 151672 KB Output is correct
28 Correct 889 ms 151800 KB Output is correct
29 Correct 882 ms 151800 KB Output is correct
30 Correct 885 ms 151628 KB Output is correct