제출 #856316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856316		vipboy0402hcm	벽 (IOI14_wall)	C++17	0 / 100	166 ms	14024 KiB

wall

#include<iostream>
#include<vector>
#include<cmath>
#include<stdio.h>
#include<numeric>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<algorithm>
#include<string>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef unsigned long long ll; 
typedef pair<int, int> ii; 
typedef vector<ii> vii;
typedef vector<int> vi;
struct lazy{
    ll height;
    ll type;
    ll query;
};
lazy ar[8000017];
vector<ii> res;
ll n,m,u,v,q,k,t;
/*void build(int id,int l,int r){
    if(l==r){
        ar[id]=0x3f3f3f3f;
        return;
    }
    int m=(l+r)/2;
    build(2*id,l,m);
    build(2*id+1,m+1,r);
    ar[id]=min(ar[2*id],ar[2*id+1]);
}
void apply(ll& a,lazy b,int len){
    if(b.a==0&&b.d==0){
        return;
    }
    else{
        a=b.assign*len;
        a+=b.add*len;
    }
}*/
void apply(lazy& a,lazy b){
    if(b.type==0){
        return;
    }
    else if(b.type==1){
        a.height=max(a.height,b.query);
        a.query=b.query;
        a.type=b.type;
    }
    else{
        a.height=min(a.height,b.query);
        a.query=b.query;
        a.type=b.type;
    }
}
void propagate(int id,int l,int r){
    if(l==r){
        return;
    }
    apply(ar[2*id],ar[id]);
    apply(ar[2*id+1],ar[id]);
}
void print(int id,int l,int r,int finalHeight[]){
	if(l==r){
        finalHeight[l]=ar[id].height;
        return;
    }
    int m=(l+r)/2;
    print(2*id,l,m,finalHeight);
    print(2*id+1,m+1,r,finalHeight);
}
void propagateAll(int id,int l,int r){
    propagate(id,l,r);
    ar[id]={ar[id].height,0,0};
    if(l==r){
        return;
    }
    int m=(l+r)/2;
    propagateAll(2*id,l,m);
    propagateAll(2*id+1,m+1,r);
}
void add(int id,int lx,int rx,int l,int r,ll t,ll a){
    propagate(id,lx,rx);
    ar[id]={ar[id].height,0,0};
    if(rx<l||lx>r){
        return;
    }
    if(lx>=l&&rx<=r){
        ar[id].height=t==1 ? max(ar[id].height,a) : min(ar[id].height,a);
        ar[id].query=a;
        ar[id].type=t;
        propagate(id,lx,rx);
        ar[id]={ar[id].height,0,0}; 
        return;
    }
    int m=(lx+rx)/2;
    add(2*id,lx,m,l,r,t,a);
    add(2*id+1,m+1,rx,l,r,t,a);
}
/*segment get(int id,int lx,int rx,int l,int r){
    apply(res[id],ar[id],rx-lx+1);
    propagate(id,lx,rx);
    ar[id]=0;
    if(rx<l||lx>r){
        return {0,0,0,0};
    }
    else if(lx>=l&&rx<=r){
        return res[id];
    }
    int m=(lx+rx)/2;
    segment a=get(2*id,lx,m,l,r);
    segment b=get(2*id+1,m+1,rx,l,r);
    return merge(a,b);
}
int find(int id,int l,int r,ll k,ll index){
    if(ar[id]!=0){
        res[id]+=ar[id];
        if(r!=l){
            ar[2*id]+=ar[id];
            ar[2*id+1]+=ar[id];
        }
        ar[id]=0;
    }
    if(index>r){
        return -1;
    }
    if(k>res[id]){
        return -1;
    }
    if(l==r){
        return l;
    }
    int m=(l+r)/2;
    int res=find(2*id,l,m,k,index);
    if(res==-1){
        res=find(2*id+1,m+1,r,k,index);
    }
    return res;
}*/
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0;i<k;i++){
		add(1,0,n-1,left[i],right[i],op[i],height[i]);
	}
	propagateAll(1,0,n-1);
	print(1,0,n-1,finalHeight);
}

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