Submission #286391

#	Time	Username	Problem	Language	Result	Execution time	Memory
286391		TadijaSebez	Constellation 3 (JOI20_constellation3)	C++11	100 / 100	834 ms	62260 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define pb push_back
const int N=200050;
const int L=20;
int a[N],lgs[N],n;
pii rmq[N][L];
pii Get(int l,int r){
	int k=lgs[r-l+1];
	return max(rmq[l][k],rmq[r-(1<<k)+1][k]);
}
pii GetRng(int x,int y){
	int top=x,bot=1,mid,L=0,R=n+1;
	while(top>=bot){
		mid=top+bot>>1;
		if(Get(mid,x).first>=y)L=mid,bot=mid+1;
		else top=mid-1;
	}
	top=n,bot=x;
	while(top>=bot){
		mid=top+bot>>1;
		if(Get(x,mid).first>=y)R=mid,top=mid-1;
		else bot=mid+1;
	}
	return {L,R};
}
int x[N],y[N],c[N],ord[N];
vector<int> stars[N];
int ls[N],rs[N];
int Build(int l,int r){
	if(r-l<2)return 0;
	pii m=Get(l+1,r-1);
	ls[m.second]=Build(l,m.second);
	rs[m.second]=Build(m.second,r);
	return m.second;
}
ll dp[N],sum[N];
int lid[N],rid[N],tid;
ll bit[N];
void Add(int i,ll x){for(;i<=n;i+=i&-i)bit[i]+=x;}
void Add(int l,int r,ll x){Add(l,x);Add(r+1,-x);}
ll Get(int i){ll ans=0;for(;i>=1;i-=i&-i)ans+=bit[i];return ans;}
void Solve(int u){
	if(!u)return;
	lid[u]=++tid;
	Solve(ls[u]);
	Solve(rs[u]);
	rid[u]=tid;
	sum[u]=dp[u]=dp[ls[u]]+dp[rs[u]];
	for(int i:stars[u]){
		dp[u]=max(dp[u],sum[u]+Get(lid[x[i]])+c[i]);
	}
	Add(lid[u],rid[u],sum[u]-dp[u]);
}
int main(){
	scanf("%i",&n);
	for(int i=1;i<=n;i++)scanf("%i",&a[i]),rmq[i][0]={a[i],i};
	a[0]=a[n+1]=n;
	for(int j=1;j<L;j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
		}
	}
	for(int i=2;i<=n;i++)lgs[i]=lgs[i>>1]+1;
	ll sum=0;
	int m;
	scanf("%i",&m);
	for(int i=1;i<=m;i++){
		scanf("%i %i %i",&x[i],&y[i],&c[i]);
		pii rng=GetRng(x[i],y[i]);
		stars[Get(rng.first+1,rng.second-1).second].pb(i);
		sum+=c[i];
	}
	int root=Build(0,n+1);
	Solve(root);
	printf("%lld\n",sum-dp[root]);
	return 0;
}

Compilation message (stderr)

constellation3.cpp: In function 'std::pair<int, int> GetRng(int, int)':
constellation3.cpp:17:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |   mid=top+bot>>1;
      |       ~~~^~~~
constellation3.cpp:23:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   mid=top+bot>>1;
      |       ~~~^~~~
constellation3.cpp: In function 'int main()':
constellation3.cpp:63:41: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   63 |    rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
      |                                        ~^~
constellation3.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
constellation3.cpp:59:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  for(int i=1;i<=n;i++)scanf("%i",&a[i]),rmq[i][0]={a[i],i};
      |                       ~~~~~^~~~~~~~~~~~
constellation3.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |  scanf("%i",&m);
      |  ~~~~~^~~~~~~~~
constellation3.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |   scanf("%i %i %i",&x[i],&y[i],&c[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65