Submission #201857

#	Time	Username	Problem	Language	Result	Execution time	Memory
201857		MvC	Fire (JOI20_ho_t5)	C++14	14 / 100	1097 ms	48572 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;
ll a[nmax],b[nmax],fw[nmax],rs[nmax];
vector<int>vc[nmax];
stack<int>st;
set<int>ad,dl[nmax];
set<int>::iterator it;
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.in(i);
		dl[r[i]-i+1].in(i);
	}
	for(i=1;i<=n;i++)
	{
		for(it=dl[i].begin();it!=dl[i].end();it++)ad.er(ad.fd(*it));
		for(it=ad.begin();it!=ad.end();it++)
		{
			upd((*it)+i,-b[(*it)+i]);
			b[(*it)+i]=a[*it];
			upd((*it)+i,b[(*it)+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