Submission #236897

# Submission time Handle Problem Language Result Execution time Memory
236897 2020-06-03T17:38:21 Z rajarshi_basu Fire (JOI20_ho_t5) C++14
Compilation error
0 ms 0 KB
#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{
	int st[2*MAXT];
	void update(int node,int ss,int se,int pos,int 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];
	}
	int 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);
	}
};


/*
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;
	int data; // depends on the event.
	Event(int a,int b,int c,int d=0){
		type = a;
		time = b;
		item = c;
		data = d;
	} 
};	


int prev_greater[MAXN];
int next_greater[MAXN];
int 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;
	});
}

SegmentTree segtree_expansion;// for expansion
SegmentTree segtree_stable;// when no expansion
SegmentTree segtree_decay;// when there is decay
SegmentTree segtree_decay_helper;

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

ll getAnsForPrefix(int x,int t){
	ll cost = 0;
	int xcp = x;
	while(x >= 0 and xcp-prev_greater[x]<=t)x = prev_greater[x];
	if(D)cout << "PREFIX: " << xcp << " " << x << endl;
	cost += segtree_expansion.get(0,0,n,0,x)*(t+1);// the expansion
	if(D)cout << "cost1 : " << cost << endl;
	cost += segtree_stable.get(0,0,n,0,x);
	if(D)cout << "cost2 : " << cost << endl;
	cost -= segtree_decay.get(0,0,n,0,x)*(t) - segtree_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);

	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);
	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)segtree_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){
				segtree_expansion.update(0,0,n,i,0);
				segtree_stable.update(0,0,n,i,arr[i]*e.time);
				growthState[i] = 0;
				stableState[i] = 1;

			}else if(e.type == 2){
				segtree_decay.update(0,0,n,i,arr[i]);
				segtree_decay_helper.update(0,0,n,i,arr[i]*e.time);
				decayState[i] = 1;
			}else{
				// the first two are redundant
				//segtree_expansion.update(0,0,n,e.item,0);
				segtree_stable.update(0,0,n,i,0);
				segtree_decay_helper.update(0,0,n,i,0);
				segtree_decay.update(0,0,n,i,0);
				decayState[i] = growthState[i] = 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

ho_t5.cpp: In function 'long long int getAnsForPrefix(long long int, long long int)':
ho_t5.cpp:159:39: error: no matching function for call to 'max(int, long long int)'
  cost -= (arr[x])*(min(max(0,t-(xcp-x)),(next_greater[x]-xcp-1)));
                                       ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from ho_t5.cpp:3:
/usr/include/c++/7/bits/stl_algobase.h:219:5: note: candidate: template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:219:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:159:39: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  cost -= (arr[x])*(min(max(0,t-(xcp-x)),(next_greater[x]-xcp-1)));
                                       ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from ho_t5.cpp:3:
/usr/include/c++/7/bits/stl_algobase.h:265:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)
     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:265:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:159:39: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  cost -= (arr[x])*(min(max(0,t-(xcp-x)),(next_greater[x]-xcp-1)));
                                       ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from ho_t5.cpp:5:
/usr/include/c++/7/bits/stl_algo.h:3462:5: note: candidate: template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)
     max(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:159:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  cost -= (arr[x])*(min(max(0,t-(xcp-x)),(next_greater[x]-xcp-1)));
                                       ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from ho_t5.cpp:5:
/usr/include/c++/7/bits/stl_algo.h:3468:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)
     max(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:159:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  cost -= (arr[x])*(min(max(0,t-(xcp-x)),(next_greater[x]-xcp-1)));
                                       ^
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:16:18: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(i,n) for(int i=0;i<n;i++)
                  ^
ho_t5.cpp:187:2: note: in expansion of macro 'FOR'
  FOR(i,n)if(D)cout << next_greater[i] << " ";if(D)cout << endl;
  ^~~
ho_t5.cpp:187:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  FOR(i,n)if(D)cout << next_greater[i] << " ";if(D)cout << endl;
                                              ^~
ho_t5.cpp:16:18: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(i,n) for(int i=0;i<n;i++)
                  ^
ho_t5.cpp:188:2: note: in expansion of macro 'FOR'
  FOR(i,n)if(D)cout << prev_greater[i] << " ";if(D)cout << endl;
  ^~~
ho_t5.cpp:188:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  FOR(i,n)if(D)cout << prev_greater[i] << " ";if(D)cout << endl;
                                              ^~
ho_t5.cpp:224:36: warning: operation on 'growthState[i]' may be undefined [-Wsequence-point]
     decayState[i] = growthState[i] = growthState[i] = 0;
                     ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~