Submission #236910

#	Time	Username	Problem	Language	Result	Execution time	Memory
236910		rajarshi_basu	Fire (JOI20_ho_t5)	C++14	100 / 100	651 ms	52684 KiB

ho_t5

#include <stdio.h>     
#include <stdlib.h>    
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
 
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long 
#define ld long double
//#define int ll
//#define int short
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<iii,int>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
//#define mp make_pair
#define vv vector
#define endl '\n'
 
using namespace std;

const int MAXN = 200*1000 + 5;
const int MAXT = 263*1000;

struct FenwickTree{
	ll BITree[MAXN];
	ll getSum(int index) { 
	    ll sum = 0;
	    index = index + 1; 
	    while (index>0){ 
	        sum += BITree[index]; 
	        index -= index & (-index); 
	    } 
	    return sum; 
	} 
	void updateBIT(int index, ll val) { 
	    index = index + 1; 
	  	while (index <= MAXN){ 
	    	BITree[index] += val; 
		    index += index & (-index); 
	    } 
	} 
	void update(int a,int b,int c,int d,ll val){
		updateBIT(d,val - get(a,b,c,d,d));
	}
	ll get(int a,int b,int c,int l,int r){
		ll cost = getSum(r);
		if(l != 0)cost -= getSum(l-1);
		return cost;
	}
};


/*
stage 1: still growing towards left. : sum of elements*time
stage 2(a): end growing and stabilise: sum of elementrange.
stage 2(b): grow and decay, hence no change: sum of element range 
stage 3: just decay: sum(elementrange) - sum(element size)*time
stage 4: dead. We dont really need to keep track of this.

// lets see how we can better the implementation. We have a period when there is a growth
and then we have a period where there is a decay. Stage 2(a/b) can be calculated in terms of those. 
stage 4 is bleh, just kick it out. 
growth_end(i) = time when growth stops. 
decay_start(i) = time when decay starts. 
dead(i) = when we dont need to consider it. 

for every viable i, ans is Arr[i]*(min(growth_end(i),t) - max(0,t-decay_start(i)))
=> Arr[i]*(min(growth_end(i),t)) - Arr[i]*(max(0,t-decay_start(i)));
*/
int D = 0;
int n;
struct Event{
	// =1 means growth_end(i) has been reached, and it wont grow anymore;
	// =2 means decay has been started.
	// type2 = ded.
	int type; 
	int time;
	int item;
	Event(int a,int b,int c){
		type = a;
		time = b;
		item = c;
	} 
};	


int prev_greater[MAXN];
int next_greater[MAXN];
ll arr[MAXN];

void generateGreaters(int n){
	stack<int> st1;
	stack<int> st2;
	FOR(i,n){
		while(!st1.empty() and arr[st1.top()] < arr[i])st1.pop();
		if(st1.empty())prev_greater[i] = -3*n;
		else prev_greater[i] = st1.top();
		st1.push(i);

		while(!st2.empty() and arr[st2.top()] <= arr[n-i-1])st2.pop();
		if(st2.empty())next_greater[n-i-1] = n;
		else next_greater[n-i-1] = st2.top();
		st2.push(n-i-1);
	}
}

vv<Event> eventlist;
void formEventList(int n){
	FOR(i,n){
		int delta1 = next_greater[i] - i;
		eventlist.pb(Event(1,delta1,i));

		int delta2 = i - prev_greater[i];
		delta2--;
		eventlist.pb(Event(2,delta2,i));

		eventlist.pb(Event(3,delta2+delta1,i));
	}
	sort(eventlist.begin(), eventlist.end(),[&](Event e1,Event e2){
		if(e1.time == e2.time)return e1.type < e2.type;
		return e1.time < e2.time;
	});
}

FenwickTree fenwick_expansion;// for expansion
FenwickTree fenwick_stable;// when no expansion
FenwickTree fenwick_decay;// when there is decay
FenwickTree fenwick_decay_helper; // basically decay is like Arr[i]*(t-somevalue), and Arr[i]*somevalue is determined by this array.

const int LOGN = 18;
ll sparseTable[LOGN][MAXN];

void generateSparseTable(){
	FOR(i,n)sparseTable[0][i] = prev_greater[i];
	FORE(i,1,LOGN-1){
		FOR(j,n){
			int p = sparseTable[i-1][j];
			if(p < 0 )sparseTable[i][j] = p;
			else sparseTable[i][j] = sparseTable[i-1][p];
		}
	}
}

ll getAnsForPrefix(int x,int t){
	ll cost = 0;
	int xcp = x;

	// here we are essentially finding the element presiding over the last element. 
	for(int goUp = LOGN-1;goUp >= 0;goUp--){
		if(sparseTable[goUp][x] >= 0 and xcp-sparseTable[goUp][x] <= t){
			x = sparseTable[goUp][x];
		}
	}


	cost += fenwick_expansion.get(0,0,n,0,x)*(t+1);// the expansion
	cost += fenwick_stable.get(0,0,n,0,x);
	cost -= fenwick_decay.get(0,0,n,0,x)*(t) - fenwick_decay_helper.get(0,0,n,0,x);
	cost -= (arr[x])*(min(max(0,t-(xcp-x)),(next_greater[x]-xcp-1)));
	return cost;
}


signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int q;
	cin >> n >> q;
	FOR(i,n)cin >> arr[i];
	iiii queries[q];
	FOR(i,q){
		int a,b,c;
		cin >> a >> b >> c;
		b--;c--;
		queries[i] = {{a,{b,c}},i};
	}
	sort(queries,queries+q);

	generateGreaters(n);
	formEventList(n);
	generateSparseTable();

	reverse(eventlist.begin(), eventlist.end()); // since we take elements from back

	FOR(i,n)fenwick_expansion.update(0,0,n,i,arr[i]);
	ll ans[q];
	for(auto f : queries){
		auto e = f.ff;
		int t = e.ff;
		int a = e.ss.ff;int b = e.ss.ss;
		// at time t, in range a to b;
		while(!eventlist.empty() and eventlist.back().time <= t){
			// we have got more events to process yay !!
			Event e = eventlist.back();eventlist.pop_back();
			int i = e.item;
			if(e.type == 1){
				fenwick_expansion.update(0,0,n,i,0);
				fenwick_stable.update(0,0,n,i,arr[i]*e.time);
			}else if(e.type == 2){
				fenwick_decay.update(0,0,n,i,arr[i]);
				fenwick_decay_helper.update(0,0,n,i,arr[i]*e.time);
			}else{
				fenwick_stable.update(0,0,n,i,0);
				fenwick_decay_helper.update(0,0,n,i,0);
				fenwick_decay.update(0,0,n,i,0);
			}
		}

		ll cost = getAnsForPrefix(b,t);
		if(a != 0)cost -= getAnsForPrefix(a-1,t);
		ans[f.ss] = cost;
	}
	FOR(i,q){
		cout << ans[i] << endl;
	}

	return 0;
}

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