Submission #1214106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214106		sitingfake	Wall (IOI14_wall)	C++20	100 / 100	686 ms	141304 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
using namespace std;

// define

#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define ll long long
#define ld double
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) (((x)>>(i))&1LL)
#define flip(x,i) ((x)^(1LL<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1

//constant

const ll mod = 1e9 + 7;
const long long linf = 4557430888798830399;
const int inf = 1061109567;
const int maxarr = 1e6 + 5;
const int dx[] = {0,1,-1,0};
const int dy[] = {1,0,0,-1};

template<typename T> bool maximize(T &a, const T &b)
{
    if(a < b) {a = b; return 1;}
    return 0;
}

template<typename T> bool minimize(T &a, const T &b)
{
    if(a > b) {a = b; return 1;}
    return 0;
}

inline void Plus(ll & a ,ll b)
{
    b %= mod;
    a += b;
    if(a >= mod) a -= mod;
    if(a < 0) a += mod;
    return;
}

inline void Mul(ll & a, ll b)
{
    a %= mod; b %= mod;
    a *= b;
    a %= mod;
    return;
}

//code
//
//const int maxn = 1e5 + 7;
//
//int op[maxn] , Left[maxn] , Right[maxn] , finalHeight[maxn] , height[maxn];
//int n , k;

struct SegTree
{
    struct Node
    {
        int Max1;
        int Max2;
        int Min1;
        int Min2;

        Node ()
        {
            Max1 = inf;
            Max2 = -inf;
            Min1 = 0;
            Min2 = inf;
        }

        Node operator + (Node & other)
        {
            Node ans;
            if(Max1 == other.Max1)
            {
                ans.Max1 = Max1;
                ans.Max2 = max(Max2 , other.Max2);
            }
            else if(Max1 > other.Max1)
            {
                ans.Max1 = Max1;
                ans.Max2 = max(Max2 , other.Max1);
            }
            else
            {
                ans.Max1 = other.Max1;
                ans.Max2 = max(Max1 , other.Max2);
            }

            if(Min1 == other.Min1)
            {
                ans.Min1 = Min1;
                ans.Min2 = min(Min2 , other.Min2);
            }
            else if(Min1 < other.Min1)
            {
                ans.Min1 = Min1;
                ans.Min2 = min(Min2 , other.Min1);
            }
            else
            {
                ans.Min1 = other.Min1;
                ans.Min2 = min(Min1 , other.Min2);
            }

            return ans;
        }
    };

    vector <Node> st;

    SegTree(int n)
    {
        st.resize(4 * (n + 2));
    }

    void Build(int i ,int l ,int r)
    {
        if(l == r)
        {
            st[i].Max1 = st[i].Min1 = 0;
            return;
        }

        int mid = (r + l) >> 1;
        Build(i * 2 , l , mid);
        Build(i * 2 + 1, mid + 1, r);
        st[i] = st[i * 2] + st[i * 2 + 1];
    }

    inline void ApplyMax(int i , int val)
    {
        if(st[i].Min1 >= val) return;

        st[i].Min1 = val;

        if(st[i].Max2 == -inf)
        {
            st[i].Max1 = val;
            return;
        }
        if(st[i].Min1 >= st[i].Max1)
        {
            st[i].Max1 = val;
        }
        else if(st[i].Min1 > st[i].Max2)
        {
            st[i].Max2 = val;
        }
    }

    inline void ApplyMin(int i ,int val)
    {
        if(st[i].Max1 <= val) return;

        st[i].Max1 = val;

        if(st[i].Min2 == inf)
        {
            st[i].Min1 = val;
            return;
        }
        if(st[i].Max1 <= st[i].Min1)
        {
            st[i].Min1 = val;
        }
        else if(st[i].Max1 < st[i].Min2)
        {
            st[i].Min2 = val;
        }
    }

    inline void Push(int i)
    {
        ApplyMax(i * 2 , st[i].Min1);
        ApplyMax(i * 2 + 1, st[i].Min1);
        ApplyMin(i * 2 , st[i].Max1);
        ApplyMin(i * 2 + 1, st[i].Max1);
    }

    void UpdateMax(int i ,int l ,int r , int u , int v , int val)
    {
        if(u > r || v < l || st[i].Min1 >= val) return;

        if(u <= l && r <= v && st[i].Min2 > val)
        {
            ApplyMax(i , val);
            return;
        }

        int mid = (r + l) >> 1;

        Push(i);
        UpdateMax(i * 2 ,l , mid , u , v , val);
        UpdateMax(i * 2 + 1, mid + 1, r, u , v, val);

        st[i] = st[i * 2] + st[i * 2 + 1];
    }

    void UpdateMin(int i ,int l ,int r ,int u, int v , int val)
    {
        if(u > r || v < l || st[i].Max1 <= val) return;

        if(u <= l && r <= v && st[i].Max2 < val)
        {
            ApplyMin(i , val);
            return;
        }

        int mid = (r + l) >> 1;

        Push(i);
        UpdateMin(i * 2 ,l , mid , u , v , val);
        UpdateMin(i * 2 + 1, mid + 1, r, u , v, val);
        st[i] = st[i * 2] + st[i * 2 + 1];
    }

    int getPos(int i , int l ,int r, int pos)
    {
        if(pos > r || pos < l) return 0;
        if(l == r) return st[i].Max1;
        int mid = (r + l) >> 1;
        Push(i);

        if(pos <= mid) return getPos(i * 2 , l , mid , pos);

        return getPos(i * 2 + 1 , mid + 1, r, pos);
    }
};

void buildWall(int n , int k , int op[] , int Left[] , int Right[] , int height[] , int finalHeight[])
{
    SegTree st(n);
    st.Build(1 ,0 , n - 1);

    for(int i = 0 ; i < k ; i++)
    {
        if(op[i] == 1)
        {
            st.UpdateMax(1 , 0 , n - 1 , Left[i] , Right[i] , height[i]);
        }
        else
        {
            st.UpdateMin(1 , 0 , n - 1 , Left[i] , Right[i] , height[i]);
        }
    }

    for(int i = 0; i < n ; i++)
    {
        finalHeight[i] = st.getPos(1 , 0 , n - 1 , i);
    }
}

//signed main()
//{
//    ios_base :: sync_with_stdio(0);
//    cin.tie(0);
//    cout.tie(0);
//
//    cin >> n >> k;
//
//    for(int i = 0; i < k ; i++)
//    {
//        cin >> op[i] >> Left[i] >> Right[i] >> height[i];
//    }
//
//    buildWall(n , k , op , Left , Right , height , finalHeight);
//
//    for(int i = 0; i < n ;i++)
//    {
//        cout << finalHeight[i] << '\n';
//    }
//
//}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39