#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];
map<pii,int> was;
ll DP(int l,int r){
if(r-l<2)return 0;
if(was.count({l,r}))return was[{l,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[{l,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
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]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5248 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5248 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5248 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
