#include "bits/stdc++.h"
using namespace std;
#define forR(i, a) for(int i = 0; (i) < (a); ++(i))
#define REP(i, a, b) for(int i = (a); (i) < (b); ++i)
#define all(a) a.begin(), a.end()
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define printArr(arr) for(int asdfg : arr) cout << asdfg << ' '; cout << '\n'
#define open(x) freopen(((string) x + ".in").c_str(), "r", stdin); freopen(((string) x + ".out").c_str(), "w", stdout);
typedef long long ll;
typedef long double ld;
struct pii{ll a, b;};
struct tii{ll a, b, c;};
bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}
#define int ll
const int MN = 2e5 + 10, ME = 4 * MN, MOD = 1e9+7;
const ll po(int b, int e){
if(e == 0) return 1;
else {
ll h = po(b, e / 2);
return e % 2 == 0 ? h * h % MOD : h * h % MOD * b % MOD;
}
}
struct node{int v, c;};
node comb(const node l, const node r){
node ret = {max(l.v, r.v), 0};
if(l.v == ret.v) ret.c += l.c;
if(r.v == ret.v) ret.c += r.c;
ret.c %= MOD;
return ret;
}
struct Seg{
node seg[ME];
void init(int n){
REP(i, 1, 4 * n + 1) seg[i] = {0, 0};
}
void upd(int i, int val, int cnt, int v, int nl, int nr){
if(nl == nr) seg[v] = {val, cnt};
else {
int mid = (nl+nr)/2;
if(i <= mid) upd(i, val, cnt, 2*v, nl, mid);
else upd(i, val, cnt, 2*v+1, mid+1, nr);
seg[v] = comb(seg[2*v], seg[2*v+1]);
}
}
node qu(int l, int r, int v, int nl, int nr){
if(l > r) return {0, 0};
else if(nl == l && nr == r) return seg[v];
else {
int mid = (nl+nr)/2;
return comb(
qu(l, min(mid, r), 2*v, nl, mid),
qu(max(mid+1,l), r, 2*v+1, mid+1, nr)
);
}
}
} seg;
void solve(int n, int v[MN], int id[MN], node ans[MN]){
seg.init(n);
vector<tii> upd;
REP(i, 1, n + 1) {
ans[i] = comb(seg.qu(id[i]+1, n, 1, 1, n), {0, 1});
ans[i].v += 1;
upd.push_back({id[i], ans[i].v, ans[i].c});
if(v[i] == n || v[i] != v[i+1]){
for(auto [ind, len, cnt] : upd) seg.upd(ind, len, cnt, 1, 1, n);
upd.clear();
}
}
// cout << '\n';
// REP(i, 1, n + 1) printf("%d ", v[i]); cout << '\n';
// REP(i, 1, n + 1) printf("%d ", id[i]); cout << '\n';
// REP(i, 1, n + 1) printf("[%d %d] ", ans[i].v, ans[i].c); cout << '\n';
}
int v[MN], id[MN];
node a1[MN], a2[MN];
pii arr[MN];
signed main(){
int n; cin >> n;
REP(i, 1, n+1) {
cin >> arr[i].b;
arr[i].a = i;
}
sort(arr+1, arr+n+1, [](pii a, pii b){return a.b < b.b;});
REP(i, 1, n + 1) v[i]=arr[i].b, id[i]=arr[i].a;
solve(n, v, id, a1);
reverse(v+1,v+1+n); reverse(id+1,id+n+1);
solve(n, v, id, a2);
node bes = {0, 0};
REP(i, 1, n + 1) bes = comb(bes, {a1[i].v + a2[n+1-i].v - 1, a1[i].c * a2[n+1-i].c});
cout << bes.v << ' ' << bes.c * po(2, n-bes.v) % MOD << '\n';
}
Compilation message
zoltan.cpp: In function 'bool operator<(pii, pii)':
zoltan.cpp:14:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
14 | bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}
| ~~~~~~~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
3 ms |
468 KB |
Output is correct |
| 8 |
Correct |
3 ms |
468 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
2 ms |
468 KB |
Output is correct |
| 11 |
Correct |
177 ms |
20096 KB |
Output is correct |
| 12 |
Correct |
152 ms |
17456 KB |
Output is correct |
| 13 |
Correct |
138 ms |
16468 KB |
Output is correct |
| 14 |
Correct |
188 ms |
17544 KB |
Output is correct |
| 15 |
Correct |
283 ms |
21760 KB |
Output is correct |
| 16 |
Correct |
292 ms |
25084 KB |
Output is correct |
| 17 |
Correct |
221 ms |
25292 KB |
Output is correct |
| 18 |
Correct |
266 ms |
25296 KB |
Output is correct |
| 19 |
Correct |
227 ms |
25292 KB |
Output is correct |
| 20 |
Correct |
238 ms |
25312 KB |
Output is correct |
