Submission #626330

#	Time	Username	Problem	Language	Result	Execution time	Memory
626330		PoPularPlusPlus	Radio Towers (IOI22_towers)	C++17	23 / 100	4030 ms	9144 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>

using namespace std;

#define vf first
#define vs second
#define mp(x,y) make_pair(x,y)

struct Seg {
	int siz = 1;
	vector<int> sums;
	void init(int n){
		while(siz < n)siz*=2;
		
		sums.assign(siz * 2, 0LL);
	}
	
	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]=max(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 max(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;

void init(int n, std::vector<int> h) {
	arr = h;
}

int max_towers(int l , int r , int d) {
	Seg st;
	int n = arr.size();
	st.init(n+1);
	set<pair<int,int>> s;
	int dp[n];
	int left[n];
	for(int i = n - 1; i >= 0; i--){
		while(s.size() && (*(s.begin())).vf <= arr[i] - d){
			left[(*(s.begin())).vs] = i;
			s.erase(s.begin());
		}
		s.insert(mp(arr[i] , i));
	}
	while(s.size()){
		left[(*(s.begin())).vs] = -1;
		s.erase(s.begin());
	}
	set<pair<int,pair<int,int>>> s1;
	//for(int i = 0; i < n; i++)cout << left[i] << ' ';
	memset(dp,0,sizeof dp);
	for(int i = l; i <= r; i++){
		dp[i] = 1;
		while(s1.size() && (*(s1.begin())).vf <= arr[i] - d){
			int pos = (*(s1.begin())).vs.vs;
			dp[pos] = max(dp[pos] , (*(s1.begin())).vs.vf);
			st.set(pos , dp[pos]);
			s1.erase(s1.begin());
		}
		if(i > 0)dp[i] = max(dp[i] , dp[i-1]);
		int cur = 1;
		int p = left[i];
		if(p >= l){
			cur += st.sum(l , p);
		}
		s1.insert(mp(arr[i] , mp(cur , i)));
	}
	while(s1.size()){
		int pos = (*(s1.begin())).vs.vs;
		dp[pos] = max(dp[pos] , (*(s1.begin())).vs.vf);
		s1.erase(s1.begin());
	}
	int ans = 0;
	for(int i = l; i <= r; i++)ans = max(ans , dp[i]);
	return ans;
}

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