제출 #716031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
716031		mseebacher	벽 (IOI14_wall)	C++17	0 / 100	172 ms	13848 KiB

wall

#include "wall.h"
//#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <functional>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

#define mp make_pair
#define f first
#define s second
#define pb push_back

typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const lld pi = 3.14159265358979323846;

struct Node{
	int mx;
	int mn;
};

struct segtree{
	int size = 0;
	vector<Node> tree;
	vector<bool> marked;
	
	void init(int n){
		int x = 1;
		while(x < n) x*=2;
		size = x;
		Node a;
		a.mx = 0;
		a.mn = 1e9;
		tree.assign(x,a);
		marked.assign(x,0);
	}
	// x1 child, x2 parent
	Node combine(Node x1,Node x2){
		x1.mx = max(x1.mx,x2.mx);
		x1.mx = min(x1.mx,x2.mn);
		x1.mn = min(x1.mn,x2.mn);
		x1.mn = max(x2.mn,x1.mx);
		return x1;
	}
	
	
	void push(int x){
		tree[2*x+1] = combine(tree[2*x+1],tree[x]);
		tree[2*x+2] = combine(tree[2*x+2],tree[x]);
		marked[x] = 0;
		marked[2*x+1] = marked[2*x+2] = 1;
	}
	
	void update(Node p,int l,int r,int x,int lx,int rx){
		if(l > r) return;
		if(l > rx || r < lx) return;
		if(lx >=l && rx <= r){
			tree[x] = combine(tree[x],p);
			marked[x] = 1;
			return;
		}
		if(marked[x]){
			push(x);
			tree[x].mx = 0;
			tree[x].mn = 1e9;
		}
		int m = (lx+rx) >> 1;
		update(p,l,r,2*x+1,lx,m);
		update(p,l,r,2*x+2,m+1,rx);
		
	}
	
	int get(int i,int x,int lx,int rx){
		if(lx == rx){
			return tree[x].mx;
		}
		if(marked[x]){
			push(x);
			tree[x].mx = 0;
			tree[x].mn = 1e9;
		}
		int m = (lx+rx) >> 1;
		if(i <= m) return get(i,2*x+1,lx,m);
		else return get(i,2*x+2,m+1,rx);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	segtree s;
	s.init(4*n);
	for(int i = 0;i<k;i++){
		Node no;
		if(op[i] == 1){
			no.mx = height[i];
			no.mn = 1e9;
		}else{
			no.mx = 0;
			no.mn = height[i];
		}
		s.update(no,left[i],right[i],0,0,s.size-1);
	}
	
	for(int i = 0;i<n;i++){
		finalHeight[i] = s.get(i,0,0,s.size-1);
	}
}

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