제출 #626358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
626358		PoPularPlusPlus	송신탑 (IOI22_towers)	C++17	14 / 100	1056 ms	2896 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>

using namespace std;

struct Seg {
	int siz = 1;
	vector<int> sums;
	void init(int n){
		while(siz < n)siz*=2;
		
		sums.assign(siz * 2, 0LL);
	}
	
	void build(vector<int>& arr  , int x , int lx , int rx){
		if(rx-lx==1){
			if(lx < (int)arr.size()){
				sums[x] = arr[lx];
			}
			return;
		}
		int m = (lx + rx) / 2;
		build(arr , 2 * x + 1 , lx , m);
		build(arr, 2 * x + 2 , m , rx);
		sums[x] = sums[2 * x + 1] + sums[2 * x + 2];
	}
	
	void build(vector<int>& arr){
		build(arr , 0 , 0 , siz);
	}
	
	void set(int i , int v , int x , int lx , int rx){
		if(rx - lx ==1){
			sums[x] = v;
			return;
		}
		int m = (lx + rx) / 2;
		if(i < m){
			set(i , v , 2 * x + 1 , lx , m);
		}
		else {
			set(i , v , 2 * x + 2 , m , rx);
		}
		sums[x]=sums[2 * x + 1] + sums[2 * x + 2];
	}
	
	void set(int x , int y){
		set(x  ,y , 0 , 0 , siz);
	}
	
	int sum(int l , int r , int x , int lx , int rx){
		if(lx >= l && rx <= r){
			return sums[x];
		}
		if(lx >= r || rx <= l)return 0;
		int m = (lx + rx) / 2;
		return sum(l , r , 2 * x + 1 , lx , m) + sum(l , r , 2 * x + 2 , m , rx);
	}
	
	int sum(int l , int r){
		return sum(l , r , 0 , 0 , siz);
	}
	
};


vector<int> arr;

Seg st;

void init(int n, std::vector<int> h) {
	arr = h;
	st.init(n+1);
	vector<int> a(n,0);
	for(int i = 0; i < n; i++){
		int cnt = 0;
		if(i - 1 < 0 || arr[i] > arr[i-1])cnt++;
		if(i + 1 == n || arr[i + 1] < arr[i])cnt++;
		if(cnt == 2)a[i] = 1;
	}
	st.build(a);
}

int max_towers(int l , int r , int d) {
	int ans = st.sum(l , r + 1) + 1;
	ans -= st.sum(l , l + 1);
	if(l != r)ans -= st.sum(r , r + 1);
	return ans;
}

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