제출 #958358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958358		hocln	벽 (IOI14_wall)	C++17	100 / 100	944 ms	102616 KiB

wall

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(v) v.begin(), v.end()
#define logg(x) (31 - __builtin_clz(x))
#define llogg(x) (63 - __builtin_clzll(x))
#define mini(v) min_element(v.begin(), v.end())
#define maxi(v) max_element(v.begin(), v.end())
#define TIME cerr << double(clock() - st) / (double)CLOCKS_PER_SEC
#define sq(a) ((a)*(a))
#ifdef hocln
#include "deb.h"
#else
#define imie(...) ""
#define debug() cerr
#endif
#include "wall.h"
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> pii;
typedef long double ld;
typedef tuple<ll, ll, ll> triple;
typedef tuple<ll, ll, ll, ll, ll> five;
typedef unsigned long long ull;
const long long INF = 4e18;
const ll inf = 2e9;
const ll MN = 3e5 + 15;
const ll MX = 2e6 + 15;
const long long MOD = 1e9 + 7;
//const long long MOD = 998244353;
const long double PI = 3.141592653589793238462643383279502884197;
template<typename T, typename T2> bool chmax(T& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<typename T, typename T2> bool chmin(T& a, const T2& b) { return a > b ? a = b, 1 : 0; }
template<typename T> using vector2 = vector<vector<T>>;
const ll dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const ll dy[] = { 1, -1, 0, 0 , 1, -1, 1, -1};
std::random_device rd;
std::mt19937 gen(rd());
ll random(ll low, ll high) { uniform_int_distribution<> dist(low, high); return dist(gen); }
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first;
    return is >> p.second;
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    for (auto &i: v) os << i << ' ';
    return os;
}
ll tc = 0;
// I hate cp
const long long NO_OPERATION = ~LLONG_MAX;
const long long TYPE = INT_MAX*4LL;
struct item{
	ll mn, mx;
	void apply(ll add, ll l) {
		if(add == NO_OPERATION) return;
		if(add < TYPE) {
			chmax(mx,add);
			chmax(mn,add);
		}
		else {
			chmin(mn,add-TYPE);
			chmin(mx,add-TYPE);
		}
	}
	item operator+(item a) {
		return item();
	}
};

struct segmtree {
	ll size = 1;
	vector<item> values;

	item NEUTRAL_ELEMENT = { 0, NO_OPERATION};

	item single(ll v) {
		return {0,v};
	}

	item merge(item a, item b) {
		return a + b;
	}
	
	void pull(ll x) {
		values[x]=merge(values[2*x+1],values[2*x+2]);
	}
	
	void push(ll x, ll lx, ll rx) {
		if(rx - lx == 1) return;
		for(int j : {0,1}) {
			chmax(values[2*x+1+j].mx,values[x].mx);
			chmax(values[2*x+1+j].mn,values[x].mx);
			chmin(values[2*x+1+j].mx,values[x].mn);
			chmin(values[2*x+1+j].mn,values[x].mn);
		}
		values[x].mx = 0;
		values[x].mn = inf;
	}

	void init(ll n) {
		size = 1;
		while (size < n) size *= 2;
		values.resize(size * 2);
	}

	void build(vector<ll>& v, ll x, ll lx, ll rx) {
		if (rx - lx == 1) {
			if (lx < (ll)v.size()) {
				values[x] = single(v[lx]);
			}
			return;
		}
		ll m = (lx + rx) / 2;
		build(v, 2 * x + 1, lx, m);
		build(v, 2 * x + 2, m, rx);
		pull(x);
	}

	void build(vector<ll>& v) {
		build(v, 0, 0, size);
	}

	void set(ll i, ll v, ll x, ll lx, ll rx) {
		push(x,lx,rx);
		if (rx - lx == 1) {
			values[x] = single(v);
			return;
		}
		ll m = (lx + rx) / 2;
		if (i < m) {
			set(i, v, 2 * x + 1, lx, m);
		}
		else set(i, v, 2 * x + 2, m, rx);
		pull(x);
	}

	void set(ll i, ll v) {
		set(i, v, 0, 0, size);
	}
	
	ll solve(ll i, ll x, ll lx, ll rx) {
		push(x,lx,rx);
		if(rx - lx == 1) {
			return values[x].mn;
		}
		ll m = (lx + rx) / 2;
		if(i < m) return solve(i,2*x+1,lx,m);
		else return solve(i,2*x+2,m,rx);
	}
	
	ll solve(ll i) {
		return solve(i,0,0,size);
	}

	item calc(ll l, ll r, ll x, ll lx, ll rx) {
		push(x,lx,rx);
		if (lx >= r || rx <= l) return NEUTRAL_ELEMENT;
		if (lx >= l && rx <= r) return values[x];
		ll m = (lx + rx) / 2;
		item v1 = calc(l, r, 2 * x + 1, lx, m);
		item v2 = calc(l, r, 2 * x + 2, m, rx);
		return merge(v1, v2);
	}

	item calc(ll l, ll r) {
		return calc(l, r, 0, 0, size);
	}
	
	void add(ll l, ll r, ll v, ll x, ll lx, ll rx) {
		push(x,lx,rx);
		if(lx >= r || rx <= l) return;
		if(lx >= l && rx <= r) {
			values[x].apply(v,rx-lx);
			return;
		}
		ll m = (lx + rx) / 2;
		add(l,r,v,2*x+1,lx,m);
		add(l,r,v,2*x+2,m,rx);
	}
	
	void add(ll l, ll r, ll v) {
		add(l,r,v,0,0,size);
	}
};
segmtree sg;
void update(ll l, ll r, ll val) {
	++r;
	sg.add(l,r,val);
}

void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]) {
	sg.init(n+5);
	for(ll i = 0;i < k;i++) {
		if(op[i] == 1) {
			update(left[i],right[i],height[i]);
		}
		else {
			update(left[i],right[i],TYPE+(ll)height[i]);
		}
	}
	for(ll i = 0;i < n;i++) finalHeight[i] = sg.solve(i);
}

//inline void solve_test() {
	//sg.init(10);
	//update(1,8,4);
	//update(4,9,1+TYPE);
	//update(3,6,5+TYPE);
	//update(0,5,3);
	//update(2,2,5);
	//update(6,7,0+TYPE);
	//ll n = 10;
	//for(int i = 0;i < sg.values.size();i++) {
		//debug()<<imie(i)imie(sg.values[i].mn)imie(sg.values[i].mx);
	//}
	//vector<ll>ans(n);
	//for(ll i = 0;i < n;i++) {
		//ans[i] = sg.solve(i);
	//}
	//cout << ans;
//}

//int main()
//{
    ////srand(chrono::steady_clock::now().time_since_epoch().count());
    ////freopen("convention2.in", "r", stdin);
    ////freopen("convention2.out", "w", stdout);
	////cout << "Case #" << tc << ": " << ans << '\n';
	////cout << fixed << setprecision(4);
    //ios::sync_with_stdio(0);
    //cin.tie(0);cout.tie(0);
    //ll t = 1;
    ////cin >> t;
    //while(t--) {
		//++tc;
        //solve_test();
    //}
//}

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