Submission #1203263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203263		vijwal	Wall (IOI14_wall)	C++20	24 / 100	886 ms	13596 KiB

wall

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

int lazy[8000005][2][2];

int n;

void build(){
    for(int i=1; i<2*n; i++){
        lazy[i][0][0]=1e9;
        lazy[i][1][0]=0;
        lazy[i][0][1]=0;
        lazy[i][1][1]=0;
    }
}

void setmax(int l, int r, int range_l, int range_r, int val, int pri){
    if (l>range_r || r<range_l)return;
    if (l>=range_l && r<=range_r){
        int x = l+n, y=r+n;
        while(x!=y){x>>=1; y>>=1;}
        lazy[x][1][0] = max(val, lazy[x][1][0]);
        lazy[x][1][1] = pri;
        return;
    }
    int mid = (l+r)/2;
    setmax(l, mid, range_l, range_r, val, pri);
    setmax(mid+1, r, range_l, range_r, val, pri);
}

void setmin(int l, int r, int range_l, int range_r, int val, int pri){
    if (l>range_r || r<range_l)return;
    if (l>=range_l && r<=range_r){
        int x = l+n, y=r+n;
        while(x!=y){x>>=1; y>>=1;}
        lazy[x][0][0] = min(val, lazy[x][0][0]);
        lazy[x][0][1] = pri;
        return;
    }
    int mid = (l+r)/2;
    setmin(l, mid, range_l, range_r, val, pri);
    setmin(mid+1, r, range_l, range_r, val, pri);
}

int n_now;
void solve(int ans[]){
    for(int i=0; i<n_now; i++){
        ans[i]=0;
        vector<vector<int>> op;
        for(int x=i+n; x>0; x>>=1){
            if(lazy[x][1][1]>0) op.push_back({lazy[x][1][1], 1, lazy[x][1][0]});
            if(lazy[x][0][1]>0) op.push_back({lazy[x][0][1], 2, lazy[x][0][0]});
        }
        sort(op.begin(), op.end(), [](vector<int> a, vector<int> b){return a[0]<b[0];});
        for(vector<int> o: op){
            if(o[1]==1) ans[i]=max(ans[i], o[2]);
            else ans[i]=min(ans[i], o[2]);
        }
    }
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalheight[]){
     n_now=N;
     n = pow(2, ceil(log2(N)));
     build();
     for(int i=0; i<k; i++){

        if(op[i] == 1){
            setmax(0, n-1, left[i], right[i], height[i], i+1);
        }
        else{
            setmin(0, n-1, left[i], right[i], height[i], i+1);
        }
     }
     solve(finalheight);
}

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