Submission #518111

#	Time	Username	Problem	Language	Result	Execution time	Memory
518111		Koosha_mv	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	612 ms	60032 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll
 
const int N=3e5+99;
 
int n,m,sum,ans,a[N],x[N],y[N],L[N],R[N],val[N],dp[N],par[N],fenwik[N];
vector<int> g[N],vec[N];
pair<int,int> p[N];
pair<pair<int,int>,int> c[N];
 
void add(int x, int val){ for(x++;x<N;x+=x&-x) fenwik[x]+=val; }
int get(int x) { int res=0; for (x++;x>0;x-=x&-x) res+=fenwik[x]; return res; }

bool cmp(int i,int j){
	return R[i]<R[j];
}
void findlr(){
	vector<int> v;
	int now=1;
	a[0]=-1,a[n+1]=-1;
	v.pb(0);
	f(i,0,m){
		while(now<=p[i].F){
			while(a[now]<=a[v.back()]){
				v.pop_back();
			}
			v.pb(now);
			now++;
		}
		int l=0,r=v.size();
		while(l+1<r){
			int mid=(l+r)>>1;
			if(a[v[mid]]<p[i].S) l=mid;
			else r=mid;
		}
		L[i]=v[l]+1;
		vec[L[i]].pb(i);
	}
	v.clear();
	v.pb(n+1);
	now=n;
	f_(i,m-1,0){
		while(now>=p[i].F){
			while(a[now]<=a[v.back()]){
				v.pop_back();
			}
			v.pb(now);
			now--;
		}
		int l=0,r=v.size();
		while(l+1<r){
			int mid=(l+r)>>1;
			if(a[v[mid]]<p[i].S) l=mid;
			else r=mid;
		}
		R[i]=v[l]-1;
	}
}
bool contain(int id,int x){
	return L[id]<=x && x<=R[id];
}
void dfs(int u){
	int sum=val[u];
	for(auto v : g[u]){
		dfs(v);
		dp[u]+=dp[v];
	}
	for(auto v : g[u]){
		add(L[u],dp[v]);
		add(L[v],-dp[v]);
		add(R[v]+1,dp[v]);
		add(R[u]+1,-dp[v]);
	}
	maxm(dp[u],val[u]+get(p[u].F));
}
void buildgraph(){
	vector<int> v;
	f_(i,n,1){
		sort(all(vec[i]),cmp);
		for(auto id : vec[i]){
			while(v.size() && R[v.back()]<=R[id]){
				par[v.back()]=id;
				g[id].pb(v.back());
				v.pop_back();
			}
			v.pb(id);
		}
	}
	for(auto id : v){
		dfs(id);
		ans+=dp[id];
	}
}
 
main(){
	cin>>n;
	f(i,1,n+1){
		cin>>a[i];
		a[i]=n-a[i];
	}
	cin>>m;
	f(i,0,m){
		cin>>c[i].F.F>>c[i].F.S>>c[i].S;
		c[i].F.S=n+1-c[i].F.S;
	}
	sort(c,c+m);
	f(i,0,m){
		val[i]=c[i].S;
		p[i].F=c[i].F.F;
		p[i].S=c[i].F.S;
		sum+=val[i];
	}
	findlr();
	buildgraph();
	cout<<sum-ans;
}

Compilation message (stderr)

constellation3.cpp: In function 'void dfs(long long int)':
constellation3.cpp:83:6: warning: unused variable 'sum' [-Wunused-variable]
   83 |  int sum=val[u];
      |      ^~~
constellation3.cpp: At global scope:
constellation3.cpp:115:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  115 | main(){
      | ^~~~

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