Submission #996221

#	Time	Username	Problem	Language	Result	Execution time	Memory
996221		Alfraganus	Wall (IOI14_wall)	C++17	100 / 100	608 ms	58452 KiB

wall

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

#define print(a) for(auto x : a) cout << x << ' '; cout << endl;

struct SegTree {

    int size = 1;
    vector<int> mins, maxs;

    SegTree (int n){
        while(size < n)
            size <<= 1;
        mins.resize(2 * size, -1);
        maxs.resize(2 * size, -1);
    }

    void add(int l,  int r, int v, int x, int lx, int rx, int lastmin = -1, int lastmax = -1){
        // cout << l << ' ' << r << ' ' << v << ' ' << x << ' ' << lx << ' ' << rx << endl;
        if(maxs[x] != -1){
            if(maxs[x] < v){
                if(lastmin <= maxs[x]){
                    if(lastmax == -1)
                        lastmax = maxs[x];
                    else
                        lastmax = min(lastmax, maxs[x]);
                }
                else
                    lastmax = lastmin;
                maxs[x] = -1;
            }
        }
        if(mins[x] != -1){
            if(mins[x] >= v and lastmax == -1)
                return;
            lastmin = max(lastmin, mins[x]);
            if(lastmax != -1)
                lastmin = min(lastmin, lastmax);
            mins[x] = -1;
        }
        // cout << lastmin << ' ' << mins[x] << ' ' << lastmax << ' ' << maxs[x] << endl;
        if(l <= lx and rx <= r){
            mins[x] = max(mins[x], v);
            if(lastmax != -1){
                if(maxs[x] == -1)
                    maxs[x] = lastmax;
                else
                    maxs[x] = min(maxs[x], lastmax);
            }
            if(maxs[x] != -1)
                maxs[x] = max(maxs[x], mins[x]);
            return;
        }
        if(r <= lx or rx <= l){
            if(lastmin != -1){
                mins[x] = max(mins[x], lastmin);
                if(maxs[x] != -1)
                    maxs[x] = max(maxs[x], mins[x]);
            }
            if(lastmax != -1){
                if(maxs[x] == -1)
                    maxs[x] = lastmax;
                else
                    maxs[x] = min(maxs[x], lastmax);
                mins[x] = min(mins[x], maxs[x]);
            }
            return;
        }
        int mid = (lx + rx) >> 1;
        add(l, r, v, (x << 1) + 1, lx, mid, lastmin, lastmax);
        add(l, r, v, (x << 1) + 2, mid, rx, lastmin, lastmax);
    }

    void add(int l, int r, int v){
        add(l, r, v, 0, 0, size);
    }

    void remove(int l, int r, int v, int x, int lx, int rx, int lastmin = -1, int lastmax = -1){
        if(maxs[x] != -1){
            if(max(lastmin, maxs[x]) <= v)
                return;
            if(lastmax == -1)
                lastmax = maxs[x];
            else
                lastmax = min(lastmax, maxs[x]);
            lastmax = max(lastmax, lastmin);
            maxs[x] = -1;
        }
        if(mins[x] != -1){
            if(mins[x] > v){
                lastmin = max(lastmin, mins[x]);
                mins[x] = -1;
                if(lastmax != -1)
                    lastmin = min(lastmin, lastmax);
            }
        }
        if(l <= lx and rx <= r){
            if(maxs[x] == -1)
                maxs[x] = v;
            else
                maxs[x] = min(maxs[x], v);
            mins[x] = max(mins[x], lastmin);
            mins[x] = min(mins[x], maxs[x]);
            return;
        }
        if(rx <= l or r <= lx){
            if(lastmax != -1){
                if(maxs[x] == -1)
                    maxs[x] = lastmax;
                else
                    maxs[x] = min(maxs[x], lastmax);
                mins[x] = min(mins[x], maxs[x]);
            }
            if(lastmin != -1){
                mins[x] = max(mins[x], lastmin);
                if(maxs[x] != -1)
                    maxs[x] = max(maxs[x], mins[x]);
            }
            return;
        }
        int mid = (lx + rx) >> 1;
        remove(l, r, v, (x << 1) + 1, lx, mid, lastmin, lastmax);
        remove(l, r, v, (x << 1) + 2, mid, rx, lastmin, lastmax);
    }

    void remove(int l, int r, int v){
        remove(l, r, v, 0, 0, size);
    }

    int query(int ind, int x, int l, int r){
        if(l + 1 == r){
            if(mins[x] == -1)
                return 0;
            return mins[x];
        }
        int mid = (l + r) >> 1;
        int ans = -1;
        if(ind < mid)
            ans = query(ind, (x << 1) + 1, l, mid);
        else
            ans = query(ind, (x << 1) + 2, mid, r);
        int left = max(0, mins[x]), right = (maxs[x] == -1 ? 1e9 : maxs[x]);
        if(left <= ans and ans <= right)
            return ans;
        else if(ans < left)
            return left;
        return right;
    }

    int query(int x){
        return query(x, 0, 0, size);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SegTree s(n);
    for(int i = 0; i < k; i ++){
        if(op[i] == 1){
            if(height[i] != 0)
                s.add(left[i], right[i] + 1, height[i]);
        }
        else
            s.remove(left[i], right[i] + 1, height[i]);
        // for(int j = 0; j < 2 * s.size - 1; j ++)
        //     cout << i + 2 << ' ' << j << ' ' << s.mins[j] << ' ' << s.maxs[j] << endl;
        // for(int i = 0; i < n; i ++)
        //     cout << s.query(i) << ' ';
        // cout << endl;
    }
    for(int i = 0; i < n; i ++)
        finalHeight[i] = s.query(i);
    // cout << endl;
    // cout << "ANSWER: " << endl;
    // for(int i = 0; i < n; i ++)
    //     finalHeight[i] = 0;
    // for(int i = 0; i < k; i ++){
    //     for(int j = left[i]; j <= right[i]; j ++){
    //         if(op[i] == 1)
    //             finalHeight[j] = max(finalHeight[j], height[i]);
    //         else
    //             finalHeight[j] = min(finalHeight[j], height[i]);
    //     }
    // }
}

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