제출 #31806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31806		top34051	벽 (IOI14_wall)	C++14	0 / 100	446 ms	23120 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
#define inf 1e9

int ans[maxn];
int ub[maxn*4], lb[maxn*4];
pair<int,int> lazy[maxn*4];

void upd(int pos,int l,int r,int ok) {
    int mid = (l+r)/2;
    int val = lazy[pos].first, type = lazy[pos].second;
    if(type==0) return ;
//    printf("------- upd %d [%d, %d] : apply {%d, %d}\n",pos,l,r,val,type);
    if(type==1) ub[pos] = max(ub[pos], val), lb[pos] = ub[pos];
    if(type==2) lb[pos] = min(lb[pos], val), ub[pos] = lb[pos];
    if(l!=r && ok) {
        upd(pos<<1,l,mid,0); upd(pos<<1|1,mid+1,r,0);
        lazy[pos<<1] = lazy[pos<<1|1] = lazy[pos];
    }
    lazy[pos] = {0,0};
//    printf("------------- cur %d [%d, %d] : %d and %d\n",pos,l,r,lb[pos],ub[pos]);
}

void build(int pos,int l,int r) {
    ub[pos] = 0; lb[pos] = 0;
    if(l==r) return ;
    int mid = (l+r)/2;
    build(pos<<1,l,mid); build(pos<<1|1,mid+1,r);
}

void update(int pos,int l,int r,int x,int y,int val,int type) {
    upd(pos,l,r,1);
    if(l>r || y<l || r<x) return ;
    if(x<=l && r<=y) {
//        printf("update %d : [%d, %d] (%d, %d) : {%d, %d}\n",pos,l,r,x,y,val,type);
        lazy[pos] = {val,type};
        return ;
    }
    int mid = (l+r)/2;
    update(pos<<1,l,mid,x,y,val,type); update(pos<<1|1,mid+1,r,x,y,val,type);
}

void query(int pos,int l,int r) {
    upd(pos,l,r,1);
    if(l==r) {
        ans[l] = lb[pos];
        return ;
    }
    int mid = (l+r)/2;
    query(pos<<1,l,mid); query(pos<<1|1,mid+1,r);
}

void buildWall(int n, int m, int type[], int L[], int R[], int val[], int ret[]) {
    int i;
    build(1,0,n-1);
    for(i=0;i<m;i++) update(1,0,n-1,L[i],R[i],val[i],type[i]);
    query(1,0,n-1);
    for(i=0;i<n;i++) ret[i] = ans[i];
    return ;
}

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