제출 #729830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
729830		nishkarsh	Radio Towers (IOI22_towers)	C++17	0 / 100	926 ms	65596 KiB

towers

#include <bits/stdc++.h>
#include "towers.h"
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
using namespace std;
ll powmod(ll base,ll exponent,ll mod){
	ll ans=1;
	if(base<0) base+=mod;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int INF = 1e9;
const ll INFLL = 4e18;
const int upperlimit = 1e5+1;
const int mod = 1e9+7;
struct info{
	int diff,len[2],start[2],end[2];
};
bool operator < (const info &a,const info &b){return(a.diff < b.diff);}
vector<info> segtree[4*upperlimit];
info merge(int differ, info &lt,info &rt){
	info ans;
	ans.diff = differ;
	if(lt.len[0]&1){
		if(lt.end[0] + differ <= rt.start[1]){
			ans.len[0] = lt.len[0] + rt.len[1];
			ans.start[0] = lt.start[0];
			ans.end[0] = rt.end[1];
		}
		else{
			ans.len[0] = lt.len[0] + rt.len[0] - 1;
			if(lt.len[0] == 1) ans.start[0] = min(lt.start[0],rt.start[0]);
			else ans.start[0] = lt.start[0];
			if(rt.len[0] == 1) ans.end[0] = min(lt.end[0],rt.end[0]);
			else ans.end[0] = rt.end[0];
		}
	}
	else{
		if(lt.end[0] - differ >= rt.start[0]){
			ans.len[0] = lt.len[0] + rt.len[0];
			ans.start[0] = lt.start[0];
			ans.end[0] = rt.end[0];
		}
		else{
			ans.len[0] = lt.len[0] + rt.len[1] - 1;
			ans.start[0] = lt.start[0];
			if(rt.len[1] == 1) ans.end[0] = max(lt.end[0],rt.end[1]);
			else ans.end[0] = rt.end[1];
		}
	}
 
	if(lt.len[1]&1){
		if(lt.end[1] - differ >= rt.start[0]){
			ans.len[1] = lt.len[1] + rt.len[0];
			ans.start[1] = lt.start[0];
			ans.end[1] = rt.end[0];
		}
		else{
			ans.len[1] = lt.len[1] + rt.len[1] - 1;
			if(lt.len[1] == 1) ans.start[1] = max(lt.start[1],rt.start[1]);
			else ans.start[1] = lt.start[1];
			if(rt.len[1] == 1) ans.end[1] = max(lt.end[1],rt.end[1]);
			else ans.end[1] = rt.end[1];
		}
	}
	else{
		if(lt.end[1] + differ <= rt.start[1]){
			ans.len[1] = lt.len[1] + rt.len[1];
			ans.start[1] = lt.start[1];
			ans.end[1] = rt.end[1];
		}
		else{
			ans.len[1] = lt.len[1] + rt.len[0] - 1;
			ans.start[1] = lt.start[1];
			if(rt.len[0] == 1) ans.end[1] = min(lt.end[1],rt.end[0]);
			else ans.end[1] = rt.end[0];
		}
	}
	return ans;
}
void calculate_node(int &par){
	int lt = par<<1;
	int rt = (par<<1)+1;
	int p1 = 0, p2 = 0,prev = 0;
	while((p1 < segtree[lt].size()) && (p2 < segtree[rt].size())){
		info temp;
		if(segtree[lt][p1].diff == INF && segtree[rt][p2].diff == INF){
			int gg = max(segtree[rt][p2].start[1],segtree[lt][p1].start[1]) - min(segtree[lt][p1].start[0],segtree[rt][p2].start[0]);
			if(gg > prev) segtree[par].pb(merge(gg,segtree[lt][p1],segtree[rt][p2]));
		}
		prev = min(segtree[lt][p1].diff,segtree[rt][p2].diff);
		segtree[par].pb(merge(prev,segtree[lt][p1],segtree[rt][p2]));
		if(segtree[lt][p1].diff < segtree[rt][p2].diff) p1++;
		else if(segtree[lt][p1].diff > segtree[rt][p2].diff) p2++;
		else{
			p1++;
			p2++;
		}
	}
}
void build(int node,int i,int j, vi &h){
	if(i==j){
		info temp;
		temp.start[0] = temp.start[1] = temp.end[0] = temp.end[1] = h[i];
		temp.len[0] = temp.len[1] = 1;
		temp.diff = INF;
		segtree[node].pb(temp);
		return;
	}
	int mid = (i+j)>>1;
	build(node<<1,i,mid,h);build((node<<1)+1,mid+1,j,h);
	calculate_node(node);
}
void query_nodes(int node,int i,int j,int &l,int &r, vi &node_list){
	if((i > r) || (l > j) || (i > j) || (l > r)) return;
	if((i >= l) && (j <= r)){ node_list.pb(node); return; }
	int mid = (i+j)>>1;
	query_nodes(node<<1,i,mid,l,r,node_list);
	query_nodes((node<<1)+1,mid+1,j,l,r,node_list);
}
int n;
vi h;
void init(int N, vi H){
	n = N;
	h = H;
	build(1,0,n-1,H);
}
int max_towers(int L, int R, int D){
	vi node_list;
	info ans;
	ans.diff = D;
	ans.len[0] = ans.len[1] = 1;
	ans.start[0] = ans.start[1] = ans.end[0] = ans.end[1] = h[L];
	L++;
	query_nodes(1,0,n-1,L,R,node_list);
	for(int node : node_list){
		auto it = lower_bound(segtree[node].begin(), segtree[node].end(),ans);
		ans = merge(D,ans,*it);
	}
	return ((ans.len[0]+1)/2);
}

컴파일 시 표준 에러 (stderr) 메시지

towers.cpp: In function 'void calculate_node(int&)':
towers.cpp:110:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |  while((p1 < segtree[lt].size()) && (p2 < segtree[rt].size())){
      |         ~~~^~~~~~~~~~~~~~~~~~~~
towers.cpp:110:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |  while((p1 < segtree[lt].size()) && (p2 < segtree[rt].size())){
      |                                      ~~~^~~~~~~~~~~~~~~~~~~~
towers.cpp:111:8: warning: unused variable 'temp' [-Wunused-variable]
  111 |   info temp;
      |        ^~~~

• 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