제출 #1113069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1113069		kiethm07	벽 (IOI14_wall)	C++11	24 / 100	537 ms	11692 KiB

wall

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

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

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

using namespace std;

typedef long long ll;
typedef long double ld;

const int inf = 1e9;
const ll linf = 1e16;
const double pi = acos(-1);

class IT{
private:
    vector<int> low, high;
public:
    IT (int n){
        low.resize(4 * n,0);
        high.resize(4 * n,inf);
    }
    void apply(int id,int x,int y){
        low[id] = max(low[id], x);
        high[id] = min(high[id], y);
        low[id] = min(low[id], high[id]);
        high[id] = max(high[id], low[id]);
    }
    void down(int id,int l,int r){
        if (l == r) return;
        apply(id * 2,low[id],high[id]);
        apply(id * 2 + 1,low[id],high[id]);
        low[id] = 0;
        high[id] = inf;
    }
    void update(int id,int l,int r,int u,int v,int f,int g){
        down(id,l,r);
        if (l > v || r < u) return;
        if (l >= u && r <= v){
            apply(id,f,g);
//            cout << l << " " << r << " " << u << " " << v << " " << low[id] << " " << high[id] << "\n";
//            down(id,l,r);
            return;
        }
        int mid = (l + r) / 2;
        update(id * 2,l,mid,u,v,f,g);
        update(id * 2 + 1,mid + 1,r,u,v,f,g);
//            cout << l << " " << r << " " << u << " " << v << " " << low[id] << " " << high[id] << "\n";

    }
    int query(int id,int l,int r,int i){
        down(id,l,r);
//        cout << l << " " << r << " " << low[id] << " " << high[id] << "\n";
        if (l > i || r < i) return -1;
        if (l == r){
            return low[id];
        }
        int mid = (l + r) / 2;
        int q1 = query(id * 2,l,mid,i);
        int q2 = query(id * 2 + 1,mid + 1,r,i);
        if (q1 == -1) return q2;
        return q1;
    }
};

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
    IT t(n);
    for (int i = 0; i < k; i++){
        int l = left[i] + 1;
        int r = right[i] + 1;
//        cout << l << " " << r << " " << op[i] << " " << height[i] << "\n";
        if (op[i] == 1) t.update(1,1,n,l,r,height[i],inf);
        if (op[i] == 2) t.update(1,1,n,l,r,0,height[i]);
    }
    for (int i = 1; i <= n; i++){
        finalHeight[i - 1] = t.query(1,1,n,i);
    }
}
//
//int main(){
//    #define TEXT "a"
//    cin.tie(0) -> sync_with_stdio(0);
//    if (fopen(TEXT".inp","r")){
//        freopen(TEXT".inp","r",stdin);
//        freopen(TEXT".out","w",stdout);
//    }
//    int n = 10, k = 6;
//    int op[k] = {1,2,2,1,1,2};
//    int left[k] = {1,4,3,0,2,6};
//    int right[k] = {8,9,6,5,2,7};
//    int height[k] = {4,1,5,3,5,0};
//    int finalHeight[n] = {};
//    buildWall(n,k,op,left,right,height,finalHeight);
//    return 0;
//}

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