제출 #282419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282419		shayan_p	벽 (IOI14_wall)	C++17	100 / 100	1516 ms	111788 KiB

wall

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

#define F first
#define S second
#define sz(s) (int(s.size()))
#define PB push_back
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int maxn = 2e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int L[4 * maxn], R[4 * maxn], val[4 * maxn];

void merge(int a, int b){
    if(R[b] <= L[a])
	L[b] = R[b] = L[a];
    else if(R[a] <= L[b])
	L[b] = R[b] = R[a];
    else
	L[b] = max(L[b], L[a]), R[b] = min(R[b], R[a]);
}
void shift(int l, int r, int id){
    if(r-l == 1){
	if(val[id] < L[id])
	    val[id] = L[id];
	else if(R[id] < val[id])
	    val[id] = R[id];
	return;
    }
    merge(id, 2*id);
    merge(id, 2*id+1);
    L[id] = 0, R[id] = inf;
}
void add(int f, int s, int t, int x, int l = 0, int r = maxn, int id = 1){
    if(s <= l || r <= f)
	return;
    shift(l, r, id);
    if(f <= l && r <= s){
	if(t == 1)
	    L[id] = x, R[id] = inf;
	else
	    L[id] = 0, R[id] = x;
	return;
    }
    int mid = (l+r) >> 1;
    add(f, s, t, x, l, mid, 2*id);
    add(f, s, t, x, mid, r, 2*id+1);
}
int ask(int pos, int l = 0, int r = maxn, int id = 1){
    shift(l, r, id);
    if(r-l == 1)
	return val[id];
    int mid = (l+r) >> 1;
    if(pos < mid)
	return ask(pos, l, mid, 2*id);
    else
	return ask(pos, mid, r, 2*id+1);
}
void buildWall(int n, int q, int task[], int f[], int s[], int h[], int ans[]){
    fill(L, L + 4 * maxn, 0);
    fill(R, R + 4 * maxn, inf);
    for(int i = 0; i < q; i++)
	add(f[i], ++s[i], task[i], h[i]);
    for(int i = 0; i < n; i++)
	ans[i] = ask(i);
}

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