Submission #286349

#	Time	Username	Problem	Language	Result	Execution time	Memory
286349		TadijaSebez	Constellation 3 (JOI20_constellation3)	C++11	35 / 100	1571 ms	161784 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],rmq[N][L],lgs[N],n;
int 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)>=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)>=y)R=mid,top=mid-1;
		else bot=mid+1;
	}
	return {L,R};
}
int x[N],y[N],c[N];
map<pii,vector<int>> stars;
vector<int> idx[N];
unordered_map<ll,ll> was;
ll DP(int l,int r){
	if(r-l<2)return 0;
	if(was.count((ll)l*N+r))return was[(ll)l*N+r];
	int m=Get(l+1,r-1);
	int fir=upper_bound(idx[m].begin(),idx[m].end(),l)-idx[m].begin();
	//int las=lower_bound(idx[m].begin(),idx[m].end(),r)-idx[m].begin();
	ll ans=DP(l,idx[m][fir])+DP(idx[m][fir],r);
	for(int i:stars[{l,r}]){
		ans=max(ans,DP(l,x[i])+c[i]+DP(x[i],r));
	}
	return was[(ll)l*N+r]=ans;

	/*vector<ll> dp;
	int L=l;
	for(int i=fir;i<las;i++){
		dp.pb(DP(L,idx[m][i]));
		L=idx[m][i];
	}
	dp.pb(DP(L,r));
	ll sum=0;
	for(ll d:dp)sum+=d;
	vector<int> pts=stars[{l,r}];
	sort(pts.begin(),pts.end(),[&](int i,int j){return x[i]<x[j];});
	ll ans=sum;
	L=l;
	int j=0;
	for(int i=fir,o=0;i<las;i++,o++){
		int mx=0;
		while(j<pts.size()&&x[pts[j]]<idx[m][i])mx=max(mx,c[pts[j]]),j++;
		ans=max(ans,sum-dp[o]+mx);
		while(j<pts.size()&&x[pts[j]]==idx[m][i])ans=max(ans,sum+c[pts[j]]),j++;
		printf("%i - ",idx[m][i]);
	}
	printf("|");
	int mx=0;
	while(j<pts.size())mx=max(mx,c[pts[j]]),j++;
	ans=max(ans,sum-dp.back()+mx);
	printf("%i %i %lld\n",l,r,ans);
	return ans;*/
}
int main(){
	scanf("%i",&n);
	for(int i=1;i<=n;i++)scanf("%i",&a[i]),rmq[i][0]=a[i],idx[a[i]].pb(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]);
		stars[GetRng(x[i],y[i])].pb(i);
		sum+=c[i];
	}
	printf("%lld\n",sum-DP(0,n+1));
	return 0;
}

Compilation message (stderr)

constellation3.cpp: In function 'std::pair<int, int> GetRng(int, int)':
constellation3.cpp:16:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |   mid=top+bot>>1;
      |       ~~~^~~~
constellation3.cpp:22:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |   mid=top+bot>>1;
      |       ~~~^~~~
constellation3.cpp: In function 'int main()':
constellation3.cpp:78:41: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   78 |    rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
      |                                        ~^~
constellation3.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
constellation3.cpp:74:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |  for(int i=1;i<=n;i++)scanf("%i",&a[i]),rmq[i][0]=a[i],idx[a[i]].pb(i);
      |                       ~~~~~^~~~~~~~~~~~
constellation3.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |  scanf("%i",&m);
      |  ~~~~~^~~~~~~~~
constellation3.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |   scanf("%i %i %i",&x[i],&y[i],&c[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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