oj.uz

Submission #729796

# Submission time Handle Problem Language Result Execution time Memory
729796 2023-04-24T15:08:05 Z nishkarsh Radio Towers (IOI22_towers) C++17
0 / 100
 939 ms 65564 KB 
#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-1];
	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);
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 552 ms 42336 KB 412th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9808 KB Output is correct
2 Incorrect 7 ms 10448 KB 1st lines differ - on the 1st token, expected: '292', found: '238'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9808 KB Output is correct
2 Incorrect 7 ms 10448 KB 1st lines differ - on the 1st token, expected: '292', found: '238'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 939 ms 65564 KB 1st lines differ - on the 1st token, expected: '11903', found: '9563'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 320 ms 22252 KB 1st lines differ - on the 1st token, expected: '7197', found: '5775'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9808 KB Output is correct
2 Incorrect 7 ms 10448 KB 1st lines differ - on the 1st token, expected: '292', found: '238'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 552 ms 42336 KB 412th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -