Submission #236909

#	Time	Username	Problem	Language	Result	Execution time	Memory
236909		rajarshi_basu	Fire (JOI20_ho_t5)	C++14	100 / 100	652 ms	55724 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 SegmentTree{
	ll st[2*MAXT];
	void update(int node,int ss,int se,int pos,ll val){
		if(pos < ss or se < pos)return;
		if(ss == se){
			st[node] = val;
			return;
		}
		int mid = (ss+se)/2;
		update(node*2+1,ss,mid,pos,val);
		update(node*2+2,mid+1,se,pos,val);
		st[node] = st[node*2+1]+st[node*2+2];
	}
	ll get(int node,int ss,int se,int l,int r){
		if(l > se or r < ss)return 0;
		if(l <= ss and se <= r)return st[node];
		int mid = (ss+se)/2;
		return get(node*2+1,ss,mid,l,r)+get(node*2+2,mid+1,se,l,r);
	}
};

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;

bool growthState[MAXN];
bool stableState[MAXN];
bool decayState[MAXN];
bool deadState[MAXN];

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;

	for(int goUp = LOGN-1;goUp >= 0;goUp--){
		if(sparseTable[goUp][x] >= 0 and xcp-sparseTable[goUp][x] <= t){
			x = sparseTable[goUp][x];
		}
	}
	//x = prev_greater[x];
	//while(x >= 0 and xcp-prev_greater[x]<=t)x = prev_greater[x];


	//if(D)cout << "PREFIX: " << xcp << " " << x << endl;
	cost += fenwick_expansion.get(0,0,n,0,x)*(t+1);// the expansion
	//if(D)cout << "cost1 : " << cost << endl;
	cost += fenwick_stable.get(0,0,n,0,x);
	//if(D)cout << "cost2 : " << cost << endl;
	cost -= fenwick_decay.get(0,0,n,0,x)*(t) - fenwick_decay_helper.get(0,0,n,0,x);
	//if(D)cout << "cost3 : " << cost << endl;
	// now fix for the right most point;
	
	cost -= (arr[x])*(min(max(0,t-(xcp-x)),(next_greater[x]-xcp-1)));
	//if(D)cout << "cost4 : " << cost << endl;
	//if(D)cout << endl;
	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());
	//
	//if(D)cout << "OUTPUT DATA : " << endl;
	//FOR(i,n)if(D)cout << next_greater[i] << " ";if(D)cout << endl;
	//FOR(i,n)if(D)cout << prev_greater[i] << " ";if(D)cout << endl;
	//if(D)cout << "EVENTS:" << endl;
	for(auto e : eventlist){
	//	if(D)cout << e.type << " " << e.item << " " << e.time << endl;
	}

	//if(D)cout << "ACTUAL OUTPUT " << endl;
	FOR(i,n)growthState[i] = 1;
	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;
		//if(D)cout << "QUERY: " << t << " " << a << " " << b << endl;
		// 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);
				growthState[i] = 0;
				stableState[i] = 1;

			}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);
				decayState[i] = 1;
			}else{
				// the first two are redundant
				//fenwick_expansion.update(0,0,n,e.item,0);
				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);
				decayState[i] = 0;growthState[i] =0; growthState[i] = 0;
				deadState[i] = 1;
			}
		}

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

	if(D)cout << endl;

	FOR(i,q){
		cout << ans[i] << endl;
	}

	return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:241:11: warning: variable 'e' set but not used [-Wunused-but-set-variable]
  for(auto e : eventlist){
           ^

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