| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1041049 |
2024-08-01T14:17:53 Z |
ssense |
Zoltan (COCI16_zoltan) |
C++14 |
|
209 ms |
20048 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <limits.h>
#include <cassert>
#define fr first
#define sc second
using namespace std;
#define int long long
const int MOD = (1e9)+7;
const int N = (3e5)+5;
pair<int, int> tree1[4*N], tree2[4*N];
pair<int, int> combine(pair<int, int> a, pair<int, int> b)
{
int mx = max(a.fr, b.fr);
int ans = 0;
if(a.fr == mx){ans+=a.sc;}
if(b.fr == mx){ans+=b.sc;}
ans%=MOD;
return make_pair(mx, ans);
}
void update1(int v, int l, int r, int pos, int val1, int val2)
{
if(pos < l || pos > r)
{
return;
}
if(l == r)
{
if(tree1[v].fr < val1)
{
tree1[v] = make_pair(val1, val2);
}
else
{
tree1[v].sc+=val2;
}
return;
}
int mid = l+r>>1;
update1(2*v+1, l, mid, pos, val1, val2);
update1(2*v+2, mid+1, r, pos, val1, val2);
tree1[v] = combine(tree1[2*v+1], tree1[2*v+2]);
}
pair<int, int> get1(int v, int l, int r, int tl, int tr)
{
if(r < tl || l > tr)
{
return make_pair(0, 0);
}
if(l >= tl && r <= tr)
{
return tree1[v];
}
int mid = l+r>>1;
return combine(get1(2*v+1, l, mid, tl, tr), get1(2*v+2, mid+1, r, tl, tr));
}
void update2(int v, int l, int r, int pos, int val1, int val2)
{
if(pos < l || pos > r)
{
return;
}
if(l == r)
{
if(tree2[v].fr < val1)
{
tree2[v] = make_pair(val1, val2);
}
else
{
tree2[v].sc+=val2;
}
return;
}
int mid = l+r>>1;
update2(2*v+1, l, mid, pos, val1, val2);
update2(2*v+2, mid+1, r, pos, val1, val2);
tree2[v] = combine(tree2[2*v+1], tree2[2*v+2]);
}
pair<int, int> get2(int v, int l, int r, int tl, int tr)
{
if(r < tl || l > tr)
{
return make_pair(0, 0);
}
if(l >= tl && r <= tr)
{
return tree2[v];
}
int mid = l+r>>1;
return combine(get2(2*v+1, l, mid, tl, tr), get2(2*v+2, mid+1, r, tl, tr));
}
void solve()
{
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
vector<int> b = a;
sort(b.begin(), b.end());
b.resize(unique(b.begin(), b.end())-b.begin());
for(int i = 0; i < n; i++)
{
a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
}
int ans = 0, count = 0;
for(int i = n-1; i >= 0; i--)
{
pair<int, int> smaller = get1(0, 0, b.size()+1, 0, a[i]-1);
smaller.sc = max(smaller.sc, 1LL);
// cout << a[i] << " SMALL: " << smaller.fr << " " << smaller.sc << endl;
pair<int, int> bigger = get2(0, 0, b.size()+1, a[i]+1, b.size()+1);
bigger.sc = max(bigger.sc, 1LL);
// cout << a[i] << " BIG: " << bigger.fr << " " << bigger.sc << endl;
if(smaller.fr + bigger.fr+1 == ans)
{
count+=(smaller.sc*bigger.sc)%MOD;
count%=MOD;
}
else if(smaller.fr + bigger.fr+1 > ans)
{
ans = smaller.fr + bigger.fr+1;
count = (smaller.sc*bigger.sc)%MOD;
}
update1(0, 0, b.size()+1, a[i], smaller.fr+1LL, smaller.sc);
update2(0, 0, b.size()+1, a[i], bigger.fr+1LL, bigger.sc);
}
cout << ans << " ";
for(int i = ans; i < n; i++)
{
count*=2;
count%=MOD;
}
cout << count << endl;
}
int32_t main()
{
int t = 1;
//cin >> t;
while(t--)
{
solve();
}
}
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
*/
Compilation message
zoltan.cpp: In function 'void update1(long long int, long long int, long long int, long long int, long long int, long long int)':
zoltan.cpp:62:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
62 | int mid = l+r>>1;
| ~^~
zoltan.cpp: In function 'std::pair<long long int, long long int> get1(long long int, long long int, long long int, long long int, long long int)':
zoltan.cpp:78:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
78 | int mid = l+r>>1;
| ~^~
zoltan.cpp: In function 'void update2(long long int, long long int, long long int, long long int, long long int, long long int)':
zoltan.cpp:100:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
100 | int mid = l+r>>1;
| ~^~
zoltan.cpp: In function 'std::pair<long long int, long long int> get2(long long int, long long int, long long int, long long int, long long int)':
zoltan.cpp:116:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
116 | int mid = l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
432 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
131 ms |
19280 KB |
Output is correct |
| 12 |
Correct |
111 ms |
18972 KB |
Output is correct |
| 13 |
Correct |
104 ms |
10496 KB |
Output is correct |
| 14 |
Correct |
147 ms |
18896 KB |
Output is correct |
| 15 |
Correct |
185 ms |
19540 KB |
Output is correct |
| 16 |
Correct |
209 ms |
19920 KB |
Output is correct |
| 17 |
Correct |
163 ms |
20048 KB |
Output is correct |
| 18 |
Correct |
159 ms |
20048 KB |
Output is correct |
| 19 |
Correct |
153 ms |
19928 KB |
Output is correct |
| 20 |
Correct |
162 ms |
19944 KB |
Output is correct |
