oj.uz

Submission #640552

# Submission time Handle Problem Language Result Execution time Memory
640552 2022-09-14T21:22:31 Z KYoA_A Zoltan (COCI16_zoltan) C++17
0 / 140
 144 ms 15164 KB 
/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define dbg(x...)
#endif

#define rep(i, a, b)	for(int i = a; i < (b); ++i)
#define rrep(a, b, c)	for(int a = (b); a > c; --a)
#define each(a, b)	for(auto& a : b)

#define sz(x)       (int)(x).size()
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(), (a).rend()

#define vi vector<int>
#define ar array

template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define rsz resize
#define bk back()

#define pi pair<int, int>
#define pl pair<ll, ll>
#define mp make_pair
#define f first
#define s second

#define pct(x) __builtin_popcount(x)
constexpr int fsb(int x) {return __builtin_ffs(x) - 1;} // first set bit
constexpr int log2(int x) {return x == 0 ? 0 : 31-__builtin_clz(x);} // floor(log2(x))
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

template <class T> bool umin(T& a, const T& b){return b<a?a=b, 1:0;}
template <class T> bool umax(T& a, const T& b){return a<b?a=b, 1:0;}

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

using ll = long long;
using ld = long double;
using str = string;

const int inf = (int)1e9 + 5;
const ll infl = (ll)1e18 + 5;
const ld PI = acos((ld)-1);
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;

/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/



template<class T> struct Seg { // comb(ID,b) = b
	const T ID{}; T comb(T a, T b) { 

		if(a.f != b.f) return max(a, b);
		return {a.f, (a.s + b.s)%MOD};
	}
	int n; vector<T> seg;
	void init(int _n) { 
		n = 1; 
		while(n < _n) n<<=1;
		seg.assign(2*n,ID); 
	}
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) { // set val at position p
		p += n;
		seg[p] = comb(seg[p], val); for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {	// sum on interval [l, r]
		T ra = ID, rb = ID; 
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra,seg[l++]);
			if (r&1) rb = comb(seg[--r],rb);
		}
		return comb(ra,rb);
	}
};

#define int ll

void solve(istream &cin = std::cin, ostream &cout = std::cout){
	int n; cin >> n;
	vi v(n); each(x, v) cin >> x;
	vi a = v;
	sort(all(a));
	a.erase(unique(all(a)), a.end());
	each(x, v) x = lb(all(a), x) - a.begin() + 1;
	
	reverse(all(v));
	rrep(i, n-1, -1) v.eb(v[i]);



	Seg<pi> s;
	s.init(n + 2);
	s.upd(0, {0, 1});

	pi ans{};

	each(x, v){
		auto y = s.query(0, x - 1);
		y.f++;
		ans = s.comb(ans, y);
		s.upd(x, y);
	}

	int z = n - ans.f;
	ll x = ans.s;
	while(z){
		x = x*2%MOD;
		--z;
	}

	x = x*((MOD + 1)/2)%MOD;

	cout << x << '\n';

}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	solve();
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Incorrect 0 ms 324 KB Output isn't correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Incorrect 1 ms 320 KB Output isn't correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 1 ms 328 KB Output isn't correct
11 Incorrect 90 ms 13492 KB Output isn't correct
12 Incorrect 80 ms 12704 KB Output isn't correct
13 Incorrect 72 ms 8456 KB Output isn't correct
14 Incorrect 107 ms 13104 KB Output isn't correct
15 Incorrect 125 ms 14212 KB Output isn't correct
16 Incorrect 144 ms 15164 KB Output isn't correct
17 Incorrect 108 ms 14412 KB Output isn't correct
18 Incorrect 110 ms 14420 KB Output isn't correct
19 Incorrect 111 ms 14396 KB Output isn't correct
20 Incorrect 109 ms 14396 KB Output isn't correct