oj.uz

답안 #443941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443941 2021-07-12T14:03:26 Z penguinhacker Zoltan (COCI16_zoltan) C++14
140 / 140
 356 ms 10956 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5, M=1e9+7;
int n, a[mxN];
ar<int, 2> ic[mxN], dc[mxN], st[1<<19];
vector<int> d;

ar<int, 2> inc(ar<int, 2> x) {
	++x[0];
	return x;
}

ar<int, 2> cmb(ar<int, 2> x, ar<int, 2> y) {
	return x[0]^y[0]?max(x, y):ar<int, 2>{x[0], (x[1]+y[1])%M};
}

void upd(int i, ar<int, 2> x, int u=1, int l=0, int r=d.size()-1) {
	if (l==r) {
		st[u]=cmb(st[u], x);
		return;
	}
	int mid=(l+r)/2;
	i<=mid?upd(i, x, 2*u, l, mid):upd(i, x, 2*u+1, mid+1, r);
	st[u]=cmb(st[2*u], st[2*u+1]);
}

ar<int, 2> qry(int ql, int qr, int u=1, int l=0, int r=d.size()-1) {
	if (l>qr||r<ql)
		return {0, 0};
	if (ql<=l&&r<=qr)
		return st[u];
	int mid=(l+r)/2;
	return cmb(qry(ql, qr, 2*u, l, mid), qry(ql, qr, 2*u+1, mid+1, r));
}

void psh(ar<int, 2> t[], int u=1, int l=0, int r=d.size()-1) {
	if (l==r) {
		t[l]=st[u];
		st[u]={};
		return;
	}
	st[u]={};
	int mid=(l+r)/2;
	psh(t, 2*u, l, mid);
	psh(t, 2*u+1, mid+1, r);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; ++i)
		cin >> a[i];
	d=vector<int>(a, a+n);
	sort(d.begin(), d.end());
	d.resize(unique(d.begin(), d.end())-d.begin());
	for (int i=n-1; ~i; --i) {
		a[i]=lower_bound(d.begin(), d.end(), a[i])-d.begin();
		upd(a[i], cmb(inc(qry(a[i]+1, d.size()-1)), {1, 1}));
	}
	psh(ic);
	for (int i=n-1; ~i; --i)
		upd(a[i], cmb(inc(qry(0, a[i]-1)), {1, 1}));
	psh(dc);
	for (int i=(int)d.size()-2; ~i; --i)
		ic[i]=cmb(ic[i], ic[i+1]);
	int l=ic[0][0];
	for (int i=0; i<d.size(); ++i) {
		l=max(l, dc[i][0]);
		if (i+1<d.size())
			l=max(l, dc[i][0]+ic[i+1][0]);
	}
	ll ans=ic[0][0]==l?ic[0][1]:0;
	for (int i=0; i<d.size(); ++i) {
		if (dc[i][0]==l)
			ans=(ans+dc[i][1])%M;
		if (i+1<d.size()&&dc[i][0]+ic[i+1][0]==l)
			ans=(ans+(ll)dc[i][1]*ic[i+1][1])%M;
	}
	for (int i=0; i<n-l; ++i)
		ans=ans*2%M;
	ans=ans*(M+1)/2%M;
	cout << l << " " << ans;
	return 0;
}

Compilation message

zoltan.cpp: In function 'int main()':
zoltan.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i=0; i<d.size(); ++i) {
      |                ~^~~~~~~~~
zoltan.cpp:74:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   if (i+1<d.size())
      |       ~~~^~~~~~~~~
zoltan.cpp:78:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i=0; i<d.size(); ++i) {
      |                ~^~~~~~~~~
zoltan.cpp:81:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   if (i+1<d.size()&&dc[i][0]+ic[i+1][0]==l)
      |       ~~~^~~~~~~~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 193 ms 9224 KB Output is correct
12 Correct 172 ms 8664 KB Output is correct
13 Correct 159 ms 6460 KB Output is correct
14 Correct 242 ms 8884 KB Output is correct
15 Correct 265 ms 10052 KB Output is correct
16 Correct 356 ms 10956 KB Output is correct
17 Correct 246 ms 9836 KB Output is correct
18 Correct 254 ms 9812 KB Output is correct
19 Correct 249 ms 9808 KB Output is correct
20 Correct 246 ms 9844 KB Output is correct