제출 #1232985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232985		thelegendary08	송신탑 (IOI22_towers)	C++17	0 / 100	4086 ms	14928 KiB

towers

#include "towers.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;

int mxd = -1;
int mx = 0;
vi V, trough, ps;
int N;
struct segtree{
	int n;
	vector<pair<int,int>>mn;
	vector<pair<int,int>>mx;
	segtree(vi &a){
		n = a.size();
		mn.resize(n * 4 + 5);
		mx.resize(n * 4 + 5);
		build(1, 0, n-1, a);
	}
	pair<int,int> mrg1(pii a, pii b){
		if(a.first < b.first)return a;
		else return b;
	}
	pair<int,int> mrg2(pii a, pii b){
		if(a.first > b.first)return a;
		else return b;
	}
	void pull(int v){
		mn[v] = mrg1(mn[v*2], mn[v*2+1]);
		mx[v] = mrg2(mx[v*2], mx[v*2+1]);
	}
	void build(int v, int l, int r, vi &a){
		// cout<<v<<' '<<l<<' '<<r<<endl;
		if(l == r){
			mn[v] = mp(a[l], l);
			mx[v] = mp(a[l], l);
			return;
		}
		int mid = (l + r) / 2;
		build(v*2, l, mid, a);
		build(v*2+1, mid + 1, r, a);
		pull(v);
	}
	void update(int v, int tl, int tr, int d, int x){
		if(tl == tr){
			mn[v] = mp(x, d); mx[v] = mp(x, d); return;
		}
		int tm = (tl + tr) / 2;
		if(tm >= d){
			update(v*2, tl, tm, d, x);
		}
		else update(v*2+1, tm+1, tr, d, x);
		pull(v);
	}
	pii maxquer(int v, int tl, int tr, int l, int r){
		if(l > r)return mp(-1e9, -1);
		if(l == tl && r == tr){
			return mx[v];
		}
		int tm = (tl + tr) / 2;
		return max(maxquer(v*2, tl, tm, l, min(r, tm)), maxquer(v*2+1, tm+1, tr, max(tm+1, l), r));
	}
	pii minquer(int v, int tl, int tr, int l, int r){
		if(l > r)return mp(1e9, -1);
		if(l == tl && r == tr){
			return mn[v];
		}
		int tm = (tl + tr) / 2;
		return min(minquer(v*2, tl, tm, l, min(r, tm)), minquer(v*2+1, tm+1, tr, max(tm+1, l), r));
	}
};
void init(int N, std::vector<int> v) {
	V = v;
	// vout(ps);
}
vi v;
vi dummy = {4};
segtree s = segtree(dummy);
int solve(int l, int r, int d){
	// cout<<l<<' '<<r<<' '<<d<<endl;
	if(r - l + 1 <= 2)return 0;
	
	pii p = s.maxquer(1, 0, N-1, l,r);
	
	int mxd = p.second;
	int mx = p.first;
	int thres = mx - d;
	if(mxd == l){
		return solve(l+1, r, d);
	}
	if(mxd == r){
		return solve(l, r-1, d);
	}
	if(s.minquer(1, 0, N-1, l, mxd - 1).first <= thres && s.minquer(1, 0, N-1, mxd+1, r).first <= thres){
		return 1 + solve(l, mxd-1, d) + solve(mxd+1, r, d);
	}
	
	return 0;
}
int max_towers(int l, int r, int d) {
	vi v;
	for(int i = l; i<=r; i++){
		v.pb(V[i]);
	}
	N = v.size();
	s = segtree(v);
	return solve(0, N-1, d) + 1; 
	//PROBLEM IS SEGTREE
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23