Submission #1086337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086337		kiethm07	Wall (IOI14_wall)	C++11	0 / 100	129 ms	14032 KiB

wall

#include <bits/stdc++.h>
#include <wall.h>

#define pii pair<int,int>
#define iii pair<int,pii>
#define fi first
#define se second

#define vi vector<int>
#define all(x) x.begin(),x.end()

#define TEXT "a"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf = 1e9 + 7;
const ld eps = 1e-8;
const double pi = acos(-1);
const int N = 2e6 + 5;

class ST{
private:
    vector<int> add, rem;
public:
    vector<int> val;
    ST(int n){
        add.resize(4 * n,-1);
        rem.resize(4 * n,inf);
        val.resize(n + 5,0);
    }
    void push(int id,int l,int r){
        if (add[id] != -1){
            if (l == r) val[l] = max(val[l],add[id]);
            else{
                add[id * 2] = max(add[id * 2],add[id]);
                add[id * 2 + 1] = max(add[id * 2 + 1],add[id]);
            }
        }
        if (rem[id] != inf){
            if (l == r) val[l] = min(val[l],rem[id]);
            else{
                rem[id * 2] = min(rem[id * 2],rem[id]);
                rem[id * 2 + 1] = min(rem[id * 2 + 1],rem[id]);
            }
        }
        add[id] = -1;
        rem[id] = inf;
    }
    void update(int id,int l,int r,int u,int v,int k,int f){
        push(id,l,r);
        if (l > v || r < u) return;
        if (l >= u && r <= v){
            if (f == 1) add[id] = k;
            if (f == 2) rem[id] = k;
            push(id,l,r);
            return;
        }
        int mid = (l + r) / 2;
        update(id * 2,l,mid,u,v,k,f);
        update(id * 2 + 1,mid + 1,r,u,v,k,f);
    }
};

void buildWall(int n,int k,int op[], int left[], int right[], int height[], int finalHeight[]){
    ST t(n);
    for (int i = 0; i < k; i++){
        int l = left[i] + 1;
        int r = right[i] + 1;
        if (op[i] == 1) t.update(1,1,n,l,r,height[i],1);
        if (op[i] == 2) t.update(1,1,n,l,r,height[i],2);
    }
    for (int i = 1; i <= n; i++){
        finalHeight[i - 1] = t.val[i];
    }
}

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