Cod sursa(job #2892907)

Utilizator DooMeDCristian Alexutan DooMeD Data 23 aprilie 2022 22:39:39
Problema Range minimum query Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll modulo = 1e9 + 7;
const int nmax = 2e5;

int v[nmax+5];
ll pre[nmax+5];

int main() {
	ifstream f("dag.in");
	ofstream g("dag.out");
	
	int n; f >> n;
	pre[0] = 1;
	for(int i=1; i<=n; i++) pre[i] = pre[i-1] * 2 % modulo;
	ll ans = 1;
	stack<int> s;
	for(int i=1; i<=n; i++) {
		f >> v[i];
		while(s.size() and v[i] > v[s.top()]) s.pop();
		if(s.empty()) ans = ans * pre[i-1] % modulo;
		else {
			ll f1 = pre[s.top() - 1];
			ll f2 = pre[i - s.top()] - 1;
			if(f2 < 0) f2 += modulo;
			ans = ans * f1 % modulo * f2 % modulo;
		}
		s.emplace(i);
	}
	g << ans;
	return 0;
}