#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
#define int long long
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define inf 1000000009
#define MOD 998244353
#define lim 200005
using namespace std;
int add(int x, int y){
if(x+y>=MOD) return x+y-MOD;
return x+y;
}
int mult(int x, int y){
return ((x%MOD) * (y%MOD))%MOD;
}
int exp(int b, int t){
int res = 1;
while(t>0){
if(t%2){
t--;
res *=b;
res%=MOD;
continue;
}
t/=2;
b*=b;
b%=MOD;
}
return res;
}
void solve(){
int n; cin >> n;
int arr[n+1];
for(int i=1; i<=n; i++) cin >> arr[i];
vi inc(1, 0), dec(1, inf);
vector<vi> past1 = {{inf}}, past2 = {{0}};
vector<vi> pref1 = {{1}}, pref2 = {{1}};
ii ans[n+1];
int maxi=0;
for(int i=n; i>=1; i--){
//cerr << "---" spc i spc "---" << endl;
int pos = lower_bound(all(inc), arr[i]) - inc.begin();
if(pos == inc.size()){
inc.pb(arr[i]);
vi v = {inf};
vi vv = {0};
past1.pb(v);
pref1.pb(vv);
}
else{
inc[pos] = arr[i];
}
past1[pos].pb(arr[i]);
int aft1 = lower_bound(all(past1[pos-1]), arr[i], greater<int>()) - past1[pos-1].begin();
//for(auto j:past1[pos-1]) cerr << j << endl;
//cerr << aft1 << endl;
int cnt1 = pref1[pos-1].back();
if(aft1>1) cnt1 -= (pref1[pos-1][aft1-1]);
if(cnt1<0) cnt1+=MOD;
pref1[pos].pb(add(pref1[pos].back(), cnt1));
int pos2 = lower_bound(all(dec), arr[i], greater<int>()) - dec.begin();
if(pos2 == dec.size()){
dec.pb(arr[i]);
vi vv = {0};
past2.pb(vv);
pref2.pb(vv);
}
else{
dec[pos2] = arr[i];
}
past2[pos2].pb(arr[i]);
int aft2 = lower_bound(all(past2[pos2-1]), arr[i]) - past2[pos2-1].begin();
//cerr << "here" << endl;
//for(auto j:past2[pos2-1]) cerr << j << endl;
//cerr << aft2 << endl;
int cnt2 = pref2[pos2-1].back();
if(aft2>1) cnt2 -= (pref2[pos2-1][aft2-1]);
if(cnt2<0) cnt2+=MOD;
pref2[pos2].pb(add(pref2[pos2].back(), cnt2));
ans[i].st = pos + pos2 -1;
ans[i].nd = mult(cnt1, cnt2);
maxi = max(maxi, ans[i].st);
//cerr << cnt1 spc cnt2 << endl;
//cerr << "wowsies" spc ans[i].st spc ans[i].nd << endl;
}
int tot=0;
for(int i=1; i<=n; i++) if(ans[i].st == maxi) tot = add(tot, ans[i].nd);
cout << maxi spc mult(tot, exp(2, n-maxi)) << endl;
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
#ifdef Local
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
/*freopen("fcolor.in","r",stdin);
freopen("fcolor.out","w",stdout);*/
int t=1;
//cin >> t;
while(t--) solve();
}
Compilation message
zoltan.cpp: In function 'void solve()':
zoltan.cpp:60:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | if(pos == inc.size()){
| ~~~~^~~~~~~~~~~~~
zoltan.cpp:83:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | if(pos2 == dec.size()){
| ~~~~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
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 |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 11 |
Incorrect |
45 ms |
19568 KB |
Output isn't correct |
| 12 |
Incorrect |
39 ms |
17704 KB |
Output isn't correct |
| 13 |
Incorrect |
38 ms |
15044 KB |
Output isn't correct |
| 14 |
Incorrect |
43 ms |
10220 KB |
Output isn't correct |
| 15 |
Incorrect |
52 ms |
12884 KB |
Output isn't correct |
| 16 |
Incorrect |
54 ms |
14776 KB |
Output isn't correct |
| 17 |
Incorrect |
100 ms |
30200 KB |
Output isn't correct |
| 18 |
Incorrect |
100 ms |
30272 KB |
Output isn't correct |
| 19 |
Incorrect |
117 ms |
31548 KB |
Output isn't correct |
| 20 |
Incorrect |
113 ms |
30356 KB |
Output isn't correct |
