#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
ll n;
ll a[200009];
vector<pll> v;
pll found[200009];
pll seg[800009];
void upd(ll v, ll tl, ll tr, ll id, pll val){
if(id < tl || id > tr)
return;
if(tl == id && tr == id){
seg[v] = val;
}
else{
ll tm = (tl+tr)/2;
upd(2*v, tl, tm, id, val);
upd(2*v+1, tm+1, tr, id, val);
if(seg[2*v].ff == seg[2*v+1].ff)
seg[v] = {seg[2*v].ff, seg[2*v].ss + seg[2*v+1].ss};
else if(seg[2*v].ff > seg[2*v+1].ff)
seg[v] = seg[2*v];
else
seg[v] = seg[2*v+1];
}
}
pll get(ll v, ll tl, ll tr, ll l, ll r){
if(l < 0)
return {0, 0};
if(tl > r || tr < l)
return {0, 0};
if(l <= tl && tr <= r){
return seg[v];
}
else{
ll tm = (tl+tr)/2;
pll t1 = get(2*v, tl, tm, l, r);
pll t2 = get(2*v+1, tm+1, tr, l, r);
if(t1.ff == t2.ff)
return {t1.ff, t1.ss + t2.ss};
else if(t1.ff > t2.ff)
return t1;
else
return t2;
}
}
pll dc[200009];
pll ac[200009];
pll tot[200009];
ll mod = 1e9+7;
ll pw(ll x, ll y){
ll ret = 1;
while(y > 0){
if(y%2)
ret = ret*x%mod;
y /= 2;
x = x*x%mod;
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n;
for(ll i = 0; i < n; ++i)
cin >> a[i];
for(ll i = 0; i < n; ++i)
v.pb({a[i], i});
sort(v.begin(), v.end());
ll i = 0, j = 0;
while(i < n){
for(j = i; j < n; ++j){
if(v[i].ff != v[j].ff)
break;
found[j] = get(1, 0, n-1, v[j].ss+1, n-1);
found[j].ff++;
if(found[j].ss == 0)
++found[j].ss;
}
for(ll k = i; k < j; ++k)
upd(1, 0, n-1, v[k].ss, found[k]);
i = j;
}
for(ll i = 0; i < n; ++i)
dc[i] = get(1, 0, n-1, i, i);
for(ll i = 0; i <= 4*n; ++i)
seg[i] = {0, 0};
reverse(v.begin(), v.end());
i = 0, j = 0;
while(i < n){
for(j = i; j < n; ++j){
if(v[i].ff != v[j].ff)
break;
found[j] = get(1, 0, n-1, v[j].ss+1, n-1);
found[j].ff++;
if(found[j].ss == 0)
++found[j].ss;
}
for(ll k = i; k < j; ++k)
upd(1, 0, n-1, v[k].ss, found[k]);
i = j;
}
for(ll i = 0; i < n; ++i){
ac[i] = get(1, 0, n-1, i, i);
}
for(ll i = 0; i < n; ++i)
tot[i] = {ac[i].ff + dc[i].ff-1, ac[i].ss*dc[i].ss%mod};
ll len = 0;
ll ans = 0;
for(ll i = 0; i < n; ++i)
len = max(len, tot[i].ff);
for(ll i = 0; i < n; ++i)
if(tot[i].ff == len){
ans += pw(2, n-len)*tot[i].ss%mod;
ans %= mod;
}
cout << len << " " << ans << "\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
3 ms |
528 KB |
Output is correct |
| 8 |
Correct |
3 ms |
504 KB |
Output is correct |
| 9 |
Correct |
3 ms |
632 KB |
Output is correct |
| 10 |
Correct |
3 ms |
504 KB |
Output is correct |
| 11 |
Incorrect |
288 ms |
24944 KB |
Output isn't correct |
| 12 |
Incorrect |
245 ms |
21808 KB |
Output isn't correct |
| 13 |
Incorrect |
225 ms |
20576 KB |
Output isn't correct |
| 14 |
Incorrect |
294 ms |
21988 KB |
Output isn't correct |
| 15 |
Incorrect |
384 ms |
26976 KB |
Output isn't correct |
| 16 |
Incorrect |
446 ms |
30820 KB |
Output isn't correct |
| 17 |
Correct |
386 ms |
31136 KB |
Output is correct |
| 18 |
Correct |
386 ms |
31128 KB |
Output is correct |
| 19 |
Correct |
389 ms |
31144 KB |
Output is correct |
| 20 |
Correct |
386 ms |
31072 KB |
Output is correct |
