| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1051343 |
2024-08-10T04:51:00 Z |
12345678 |
Žarulje (COI15_zarulje) |
C++17 |
|
101 ms |
24812 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=2e5+5, mod=1e9+7;
ll n, q, a[nx], f[nx], inv[nx], res[nx], x;
vector<ll> v[nx];
struct minsegtree
{
pair<pair<ll, ll>, pair<ll, ll>> d[4*nx];
pair<pair<ll, ll>, pair<ll, ll>> merge(pair<pair<ll, ll>, pair<ll, ll>> lhs, pair<pair<ll, ll>, pair<ll, ll>> rhs)
{
if (lhs.first<=rhs.first)
{
if (lhs.second<=rhs.first) return lhs;
return {lhs.first, rhs.first};
}
else
{
if (rhs.second<=lhs.first) return rhs;
return {rhs.first, lhs.first};
}
}
void build(int l, int r, int i)
{
if (l==r) return d[i]={{a[l], l}, {1e18, 0}}, void();
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=merge(d[2*i], d[2*i+1]);
//cout<<"here "<<l<<' '<<r<<' '<<d[i].first.first<<' '<<d[i].second.first<<'\n';
}
pair<pair<ll, ll>, pair<ll, ll>> query(int l, int r, int i, int ql, int qr)
{
if (qr<l||r<ql) return {{1e18, 0}, {1e18, 0}};
if (ql<=l&&r<=qr) return d[i];
int md=(l+r)/2;
return merge(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
}
} mn;
struct segtree
{
ll d[4*nx];
void build(int l, int r, int i)
{
d[i]=1;
if (l==r) return;
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
}
void update(int l, int r, int i, int ql, int qr, ll vl)
{
if (qr<l||r<ql) return;
if (ql<=l&&r<=qr) return d[i]=(d[i]*vl)%mod, void();
int md=(l+r)/2;
update(l, md, 2*i, ql, qr, vl);
update(md+1, r, 2*i+1, ql, qr, vl);
}
void query(int l, int r, int i)
{
if (l==r) return res[l]=d[i], void();
int md=(l+r)/2;
d[2*i]=(d[2*i]*d[i])%mod;
d[2*i+1]=(d[2*i+1]*d[i])%mod;
query(l, md, 2*i);
query(md+1, r, 2*i+1);
}
} s;
ll binpow(ll x, ll y)
{
if (y==0) return 1;
auto tmp=binpow(x, y/2);
if (y%2) return ((tmp*tmp)%mod*x)%mod;
else return (tmp*tmp)%mod;
}
ll combination(ll x, ll y)
{
return (((f[x+y]*inv[x])%mod)*inv[y])%mod;
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>q;
for (int i=1; i<=n; i++) cin>>a[i], v[a[i]].push_back(i);
mn.build(1, n, 1);
s.build(1, n, 1);
cout<<"debug "<<mn.d[1].first.first<<' '<<mn.d[1].second.first<<'\n';
f[0]=1;
for (int i=1; i<=n; i++) f[i]=(f[i-1]*i)%mod;
inv[n]=binpow(f[n], mod-2);
for (int i=n-1; i>=1; i--) inv[i]=(inv[i+1]*(i+1))%mod; //cout<<"debug "<<i<<' '<<inv[i]<<' '<<(inv[i]*f[i])%mod<<'\n';
for (int t=1; t<=200000; t++)
{
int sz=v[t].size();
if (sz<2) continue;
vector<int> pref(sz), suf(sz);
for (int i=0; i<sz; i++)
{
if (i==0||(v[t][i]-1!=v[t][i-1]&&mn.query(1, n, 1, v[t][i-1]+1, v[t][i]-1).first.first<t)) pref[i]=1;
else pref[i]=pref[i-1]+1;
}
for (int i=sz-1; i>=0; i--)
{
if (i==sz-1||(v[t][i]+1!=v[t][i+1]&&mn.query(1, n, 1, v[t][i]+1, v[t][i+1]-1).first.first<t)) suf[i]=1;
else suf[i]=suf[i+1]+1;
}
for (int i=0; i<sz-1; i++)
{
auto tmp=mn.query(1, n, 1, v[t][i]+1, v[t][i+1]-1);
if (v[t][i]+1!=v[t][i+1]&&tmp.first.first>t) s.update(1, n, 1, v[t][i]+1, v[t][i+1]-1, combination(pref[i], suf[i+1]));
else if (v[t][i]+1!=v[t][i+1]&&tmp.second.first>t) s.update(1, n, 1, tmp.first.second, tmp.first.second, combination(pref[i], suf[i+1]));
}
for (int i=1; i<sz-1; i++) if (mn.query(1, n, 1, v[t][i-1]+1, v[t][i+1]-1).first.first>=t) s.update(1, n, 1, v[t][i], v[t][i], combination(pref[i-1], suf[i+1]));
}
s.query(1, n, 1);
while (q--) cin>>x, cout<<res[x]<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
101 ms |
24812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
