제출 #1203795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203795		vijwal	벽 (IOI14_wall)	C++20	0 / 100	189 ms	8264 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;}
        if((val >= lazy[x][1][0]) || (lazy[x][1][1] < lazy[x][0][1] && (lazy[x][0][0] < val || val > lazy[x][1][0]))){
            lazy[x][1][0] = val;
            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;}
        if(val <=lazy[x][0][0] || (lazy[x][0][1] < lazy[x][1][1] && ((lazy[x][0][0] > val || val < lazy[x][1][0])))){
            lazy[x][0][0] = val;
            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_act;
void solve(int ans[]){
    for(int i=0; i<n_act; 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];});
        if(i==4)cout<<ans[i]<<endl;
        for(vector<int> o: op){
            if(o[1]==1) ans[i]=max(ans[i], o[2]);
            else ans[i]=min(ans[i], o[2]);
            if(i==4)cout<<ans[i]<<' '<<o[0]<<endl;
        }
    }
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalheight[]){
     n_act=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);
}
/*
int main(){
    int a[10];
    const int v=8;
    int b[v] = {1,2,2,1,1,2,1,2};
    int c[v] = {1,4,3,0,2,6,7,4};
    int d[v] = {8,9,6,5,2,7,9,7};
    int e[v] = {4,1,5,3,5,0,1,2};
    buildWall(10, 6, b, c, d, e, a);
    for(int i=0; i<n_act; i++){cout << a[i] << ' ';}
}
*/

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