| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 202052 |
2020-02-13T09:46:18 Z |
SamAnd |
Zoltan (COCI16_zoltan) |
C++17 |
|
575 ms |
28520 KB |
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 200005, M = 1000000007;
int n;
int a[N];
int ast[N];
pair<int, int> t[N * 4][2];
pair<int, int> mer(const pair<int, int>& l, const pair<int, int>& r)
{
if (l.first > r.first)
return l;
if (l.first < r.first)
return r;
return m_p(l.first, (l.second + r.second) % M);
}
void ubd(int tl, int tr, int x, pair<int, int> y, int z, int pos)
{
if (tl == tr)
{
if (y.first > t[pos][z].first)
{
t[pos][z] = y;
}
else if (y.first == t[pos][z].first)
{
t[pos][z].second = (t[pos][z].second + y.second) % M;
}
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubd(tl, m, x, y, z, pos * 2);
else
ubd(m + 1, tr, x, y, z, pos * 2 + 1);
t[pos][z] = mer(t[pos * 2][z], t[pos * 2 + 1][z]);
}
pair<int, int> qry(int tl, int tr, int l, int r, int z, int pos)
{
if (l > r)
return m_p(0, 0);
if (tl == l && tr == r)
return t[pos][z];
int m = (tl + tr) / 2;
return mer(qry(tl, m, l, min(m, r), z, pos * 2),
qry(m + 1, tr, max(m + 1, l), r, z, pos * 2 + 1));
}
pair<int, int> ans[N * 2][2];
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
int z = 0;
vector<int> v;
map<int, int> mp;
for (int i = 1; i <= n; ++i)
v.push_back(a[i]);
sort(v.begin(), v.end());
for (int i = 0; i < n; ++i)
{
if (!i || v[i] != v[i - 1])
mp[v[i]] = ++z;
}
for (int i = 1; i <= n; ++i)
a[i] = mp[a[i]];
ast[0] = 1;
for (int i = 1; i <= n; ++i)
ast[i] = (ast[i - 1] * 2) % M;
//////////////////////////////////////////////
for (int i = n; i > 1; --i)
{
ans[n - i + 1][0] = qry(1, z, 1, a[i] - 1, 0, 1);
if (ans[n - i + 1][0].second)
++ans[n - i + 1][0].first;
ans[n - i + 1][0] = mer(ans[n - i + 1][0], m_p(1, 1));
ubd(1, z, a[i], ans[n - i + 1][0], 0, 1);
}
ans[n][1] = qry(1, z, 1, a[1] - 1, 0, 1);
if (ans[n][1].second)
++ans[n][1].first;
ans[n][1] = mer(ans[n][1], m_p(1, 1));
ubd(1, z, a[1], ans[n][1], 1, 1);
for (int i = 2; i <= n; ++i)
{
ans[n + i - 1][0] = qry(1, z, 1, a[i] - 1, 0, 1);
if (ans[n + i - 1][0].second)
++ans[n + i - 1][0].first;
ans[n + i - 1][0] = mer(ans[n + i - 1][0], m_p(1, 1));
ubd(1, z, a[i], ans[n + i - 1][0], 0, 1);
ans[n + i - 1][1] = qry(1, z, 1, a[i] - 1, 1, 1);
if (ans[n + i - 1][1].second)
++ans[n + i - 1][1].first;
ubd(1, z, a[i], ans[n + i - 1][1], 1, 1);
}
pair<int, int> yans[2] = {};
for (int i = 1; i < n * 2; ++i)
{
yans[1] = mer(yans[1], ans[i][1]);
yans[0] = mer(yans[0], ans[i][0]);
}
yans[0].second = (yans[0].second * 1LL * ast[n - yans[0].first - 1]) % M;
yans[1].second = (yans[1].second * 1LL * ast[n - yans[1].first]) % M;
yans[0] = mer(yans[0], yans[1]);
printf("%d %d\n", yans[0].first, yans[0].second);
return 0;
}
Compilation message
zoltan.cpp: In function 'int main()':
zoltan.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
zoltan.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
6 ms |
504 KB |
Output is correct |
| 8 |
Correct |
6 ms |
504 KB |
Output is correct |
| 9 |
Correct |
6 ms |
504 KB |
Output is correct |
| 10 |
Correct |
6 ms |
380 KB |
Output is correct |
| 11 |
Correct |
297 ms |
24044 KB |
Output is correct |
| 12 |
Correct |
261 ms |
21900 KB |
Output is correct |
| 13 |
Correct |
246 ms |
17136 KB |
Output is correct |
| 14 |
Correct |
376 ms |
22252 KB |
Output is correct |
| 15 |
Correct |
476 ms |
25708 KB |
Output is correct |
| 16 |
Correct |
575 ms |
28520 KB |
Output is correct |
| 17 |
Correct |
408 ms |
26348 KB |
Output is correct |
| 18 |
Correct |
414 ms |
26472 KB |
Output is correct |
| 19 |
Correct |
412 ms |
26340 KB |
Output is correct |
| 20 |
Correct |
403 ms |
26344 KB |
Output is correct |
