Submission #201867

#	Time	Username	Problem	Language	Result	Execution time	Memory
201867		zscoder	Fire (JOI20_ho_t5)	C++17	100 / 100	549 ms	46328 KiB

ho_t5

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int N = 200011;

struct Fenwick
{
	vector<ll> t;
    Fenwick(int n)
    {
        t.assign(n+1,0);
    }
    void reset(int n)
    {
		t.assign(n+1, 0);
	}
    void update(int p, ll v)
    {
        for (; p < (int)t.size(); p += (p&(-p))) t[p] += v;
    }
    ll query(int r) //finds [1, r] sum
    {                     
        ll sum = 0;
        for (; r; r -= (r&(-r))) sum += t[r];
        return sum;
    }
    ll query(int l, int r) //finds [l, r] sum
    {
		if(l == 0) return query(r);
		return query(r) - query(l-1);
	}
};

vector<ii> queries[N+11];
ll ans[N+11];
ll a[N+11];
int par[N+11];
const int C = N+4;
Fenwick F(2*N+11),F2(2*N+11),Fsum(2*N+11),F2sum(2*N+11);
Fenwick F3(2*N+11),F3sum(2*N+11);
ll shift=-C;
int subsiz[N+11];
vi adj[N+11];
ll summax;

void addval(int x, ll val)
{
	F2.update(x-shift,val);
	F2sum.update(x-shift,val*(x-shift));
}

int calcsiz(int u)
{
	subsiz[u]=1;
	for(int v:adj[u])
	{
		subsiz[u]+=subsiz[v];
	}
	return subsiz[u];
}

void quit(int id)
{
	ll subsz = calcsiz(id);
	if(par[id]!=-1)
	{
		subsz+=(id-par[id]-1);
		ll val = a[par[id]]-a[id];
		F2.update(subsz-shift,-val);
		F2sum.update(subsz-shift,-val*1LL*(subsz-shift));
		F.update(subsz+C,val);
		Fsum.update(subsz+C,val*subsz);
	}
	//if(par[id]!=-1) subsz--;
}

ll query(int t)
{
	ll sum1 = Fsum.query(1,t+C)+ll(t)*F.query(t+C+1,2*N+10);
	ll sum2 = F2sum.query(1,t-shift)+ll(shift)*F2.query(1,t-shift)+ll(t)*F2.query(t-shift+1,2*N+10);
	sum2+=F3sum.query(t+1+C,2*N+10)-F3.query(t+1+C,2*N+10)*ll(t);
	return sum1+sum2+summax;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,q; cin>>n>>q;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<q;i++)
	{
		int t,l,r; cin>>t>>l>>r;
		l--; r--;
		queries[r].pb({i,t});
		if(l>0) queries[l-1].pb({i,-t});
	}	
	memset(par,-1,sizeof(par));
	for(int i=0;i<n;i++)
	{
		//add the value
		summax+=a[i];
		if(i==0)
		{
			//addval(0,a[0]); 
			//summax+=a[0];
		}
		else
		{
			int cur=i-1;
			while(cur>=0&&a[i]>=a[cur])
			{
				quit(cur);
				cur=par[cur];
			}
			shift++;
			par[i]=cur;
			//int val = 0; 
			//if root then initial value = 1
			if(par[i]!=-1) 
			{
				summax-=(a[par[i]]-a[i])*1LL*(i-par[i]-1);
				F3.update(i-par[i]-1+C,a[par[i]]-a[i]);
				F3sum.update(i-par[i]-1+C,(i-par[i]-1)*1LL*(a[par[i]]-a[i]));
				//cerr<<"ADD VAL (NODE = "<<i<<") : "<<1+i-par[i]-1<<'\n';
				addval(1+i-par[i]-1,a[par[i]]-a[i]);
				adj[par[i]].pb(i);
			}
			//else summax+=a[i];
		}
		//solve the queries
		for(ii x:queries[i])
		{
			ll tmp = query(abs(x.se));
			ll sum=0;
			for(int j=0;j<=i;j++)
			{
				ll mx=0;
				for(int k=j;k>=max(0,j-(abs(x.se)));k--)
				{
					mx=max(mx,a[k]);
				}
				sum+=mx;
			}
			//cerr<<"QUERY TILL "<<i<<" WITH T = "<<abs(x.se)<<": "<<tmp<<' '<<sum<<'\n';
			if(x.se<0)
			{
				ans[x.fi]-=tmp;
			}
			else
			{
				ans[x.fi]+=tmp;
			}
		}
	}
	for(int i=0;i<q;i++)
	{
		cout<<ans[i]<<'\n';
	}
}

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