oj.uz

답안 #443728

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443728 2021-07-11T19:08:17 Z penguinhacker Zoltan (COCI16_zoltan) C++14
112 / 140
 308 ms 10992 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+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
112.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 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 320 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Incorrect 2 ms 332 KB Output isn't correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 191 ms 9348 KB Output is correct
12 Correct 163 ms 8640 KB Output is correct
13 Correct 149 ms 6296 KB Output is correct
14 Incorrect 216 ms 8948 KB Output isn't correct
15 Incorrect 266 ms 10052 KB Output isn't correct
16 Incorrect 308 ms 10992 KB Output isn't correct
17 Correct 295 ms 9784 KB Output is correct
18 Correct 237 ms 9772 KB Output is correct
19 Correct 237 ms 9844 KB Output is correct
20 Correct 236 ms 9840 KB Output is correct