Submission #288871

#	Time	Username	Problem	Language	Result	Execution time	Memory
288871		mohammedehab2002	Constellation 3 (JOI20_constellation3)	C++11	35 / 100	1590 ms	28536 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;
long long w[200005],ans;
vector<int> v[200005];
pair<pair<int,int>,int> s[200005];
int a[200005],pre[200005],nex[200005];
int main()
{
	int n,m;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i]=n-a[i];
	}
	scanf("%d",&m);
	for (int i=0;i<m;i++)
	{
		scanf("%d%d%d",&s[i].first.second,&s[i].first.first,&s[i].second);
		s[i].first.first=n-s[i].first.first+1;
		ans+=s[i].second;
	}
	sort(s,s+m);
	reverse(s,s+m);
	for (int i=0;i<m;i++)
	v[s[i].first.second].push_back(i);
	stack<int> st;
	set<pair<int,int> > idx;
	st.push(0);
	idx.insert({0,0});
	for (int i=1;i<=n;i++)
	{
		while (!st.empty() && a[i]<=a[st.top()])
		{
			idx.erase({a[st.top()],st.top()});
			st.pop();
		}
		for (int j:v[i])
		pre[j]=(*prev(idx.upper_bound({s[j].first.first,-1}))).second+1;
		st.push(i);
		idx.insert({a[i],i});
	}
	while (!st.empty())
	st.pop();
	idx.clear();
	st.push(n+1);
	idx.insert({0,n+1});
	for (int i=n;i>0;i--)
	{
		while (!st.empty() && a[i]<=a[st.top()])
		{
			idx.erase({a[st.top()],st.top()});
			st.pop();
		}
		for (int j:v[i])
		nex[j]=(*prev(idx.upper_bound({s[j].first.first,-1}))).second-1;
		st.push(i);
		idx.insert({a[i],i});
	}
	for (int i=0;i<m;i++)
	{
		long long v=s[i].second+w[s[i].first.second];
		if (v>0)
		{
			ans-=v;
			for (int j=pre[i];j<=nex[i];j++)
			w[j]-=v;
		}
	}
	printf("%lld",ans);
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
constellation3.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
constellation3.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |  scanf("%d",&m);
      |  ~~~~~^~~~~~~~~
constellation3.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |   scanf("%d%d%d",&s[i].first.second,&s[i].first.first,&s[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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