Submission #201858

#	Time	Username	Problem	Language	Result	Execution time	Memory
201858		MvC	Fire (JOI20_ho_t5)	C++14	14 / 100	1094 ms	28524 KiB

ho_t5

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e5+50;
const int mod=1e9+7;
using namespace std;
int n,q,i,lf[nmax],rg[nmax],x,r[nmax],j,v[nmax];
ll a[nmax],b[nmax],fw[nmax],rs[nmax];
vector<int>vc[nmax],ad,dl[nmax],nw;
stack<int>st;
void upd(int i,ll vl)
{
	for(;i<=n;i+=i&(-i))fw[i]+=vl;
}
ll qry(int i)
{
	ll rs=0;
	for(;i>=1;i-=i&(-i))rs+=fw[i];
	return rs;
}
ll qry(int l,int r)
{
	ll rs=qry(r);
	if(l>1)rs-=qry(l-1);
	return rs;
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>q;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=q;i++)
	{
		cin>>x>>lf[i]>>rg[i];
		vc[x].pb(i);
	}
	/*for(i=1;i<=n;i++)
	{
		while(!st.empty() && a[st.top()]<=a[i])st.pop();
		if(st.empty())l[i]=1;
		else l[i]=st.top()+1;
		st.push(i);
	}
	while(!st.empty())st.pop();*/
	for(i=n;i>=1;i--)
	{
		while(!st.empty() && a[st.top()]<=a[i])st.pop();
		if(st.empty())r[i]=n;
		else r[i]=st.top()-1;
		st.push(i);
	}
	for(i=1;i<=n;i++)
	{
		b[i]=a[i];
		upd(i,a[i]);
		ad.pb(i);
		v[i]=1;
		dl[r[i]-i+1].pb(i);
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<(int)dl[i].size();j++)v[dl[i][j]]=0;
		nw.clear();
		for(j=0;j<(int)ad.size();j++)if(v[ad[j]])nw.pb(ad[j]);
		ad=nw;
		for(j=0;j<(int)ad.size();j++)
		{
			upd(ad[j]+i,-b[ad[j]+i]);
			b[ad[j]+i]=a[ad[j]];
			upd(ad[j]+i,b[ad[j]+i]);
		}
		for(j=0;j<(int)vc[i].size();j++)
		{
			rs[vc[i][j]]=qry(lf[vc[i][j]],rg[vc[i][j]]);
		}
	}
	for(i=1;i<=q;i++)cout<<rs[i]<<'\n';
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80