| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 548029 |
2022-04-12T09:00:01 Z |
FEDIKUS |
Zoltan (COCI16_zoltan) |
C++17 |
|
348 ms |
26200 KB |
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
#define fb(i,s,f) for(ll (i)=s-1;(i)>=f;(i)--)
#define ffi(i,s,f) for(ll (i)=s;(i)<=(f);(i)++)
#define fbi(i,s,f) for(ll (i)=s;(i)>=(f);(i)--)
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,ll) sort(a.begin(),a.end(),greater<ll>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define ub(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef pair<ll,ll> pll;
typedef string str;
const ll maxn=2e5+10;
const ll mod=1e9+7;
ll niz[maxn];
ll compr[maxn];
pii seginc[4*maxn];
pii segdec[4*maxn];
pii incr[maxn];
pii decr[maxn];
ll n;
ll add(ll a,ll b){
return (a+b)%mod;
}
ll mul(ll a,ll b){
return a*b%mod;
}
ll pwr(ll a,ll b){
ll ret=1;
while(b){
if(b&1) ret=mul(ret,a);
b/=2;
a=mul(a,a);
}
return ret;
}
pii comb(const pii a,const pii b){
pii ret;
if(a.xx==b.xx) ret={a.xx,add(a.yy,b.yy)};
else ret=max(a,b);
return ret;
}
void update(ll t,pii v,pii *seg,ll ind=1,ll l=0,ll r=n-1){
if(l==r){
seg[ind]=v;
return;
}
ll mid=l+(r-l)/2;
if(t<=mid) update(t,v,seg,2*ind,l,mid);
else update(t,v,seg,2*ind+1,mid+1,r);
seg[ind]=comb(seg[2*ind],seg[2*ind+1]);
}
pii query(ll tl,ll tr,pii *seg,ll ind=1,ll l=0,ll r=n-1){
if(tl<=l && r<=tr) return seg[ind];
ll mid=l+(r-l)/2;
pii ret={0,0};
if(tl<=mid) ret=comb(ret,query(tl,tr,seg,2*ind,l,mid));
if(tr>mid) ret=comb(ret,query(tl,tr,seg,2*ind+1,mid+1,r));
return ret;
}
void solve(){
cin>>n;
ff(i,0,n){
cin>>niz[i];
compr[i]=niz[i];
}
sort(compr,compr+n);
ff(i,0,n){
niz[i]=lower_bound(compr,compr+n,niz[i])-compr;
}
fb(i,n,0){
{//decr
pii qry;
if(niz[i]>0) qry=query(0,niz[i]-1,segdec);
else qry={0,0};
qry.xx++;
qry=max(qry,mp(1LL,1LL));
update(niz[i],qry,segdec);
incr[i]=qry;
}
{//incr
pii qry;
if(niz[i]<n-1) qry=query(niz[i]+1,n-1,seginc);
else qry={0,0};
qry.xx++;
qry=max(qry,mp(1LL,1LL));
update(niz[i],qry,seginc);
decr[i]=qry;
}
}
pii res=mp(0,0);
ff(i,0,n){
pii tren={incr[i].xx+decr[i].xx-1,mul(incr[i].yy,decr[i].yy)};
if(res.xx==tren.xx) res.yy=add(res.yy,tren.yy);
else res=max(res,tren);
}
cout<<res.xx<<" "<<mul(res.yy,pwr(2,n-res.xx));
}
int main(){
ios;
ll t=1;
// cin>>t;
while(t--) solve();
return 0;
}
Compilation message
zoltan.cpp: In function 'void solve()':
zoltan.cpp:9:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
9 | #define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
| ^
zoltan.cpp:89:5: note: in expansion of macro 'ff'
89 | ff(i,0,n){
| ^~
zoltan.cpp:9:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
9 | #define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
| ^
zoltan.cpp:94:5: note: in expansion of macro 'ff'
94 | ff(i,0,n){
| ^~
zoltan.cpp:10:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
10 | #define fb(i,s,f) for(ll (i)=s-1;(i)>=f;(i)--)
| ^
zoltan.cpp:97:5: note: in expansion of macro 'fb'
97 | fb(i,n,0){
| ^~
zoltan.cpp:9:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
9 | #define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
| ^
zoltan.cpp:118:5: note: in expansion of macro 'ff'
118 | ff(i,0,n){
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
1 ms |
468 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
1 ms |
468 KB |
Output is correct |
| 11 |
Correct |
226 ms |
24180 KB |
Output is correct |
| 12 |
Correct |
188 ms |
23120 KB |
Output is correct |
| 13 |
Correct |
164 ms |
14620 KB |
Output is correct |
| 14 |
Correct |
230 ms |
23224 KB |
Output is correct |
| 15 |
Correct |
286 ms |
24792 KB |
Output is correct |
| 16 |
Correct |
348 ms |
26044 KB |
Output is correct |
| 17 |
Incorrect |
273 ms |
26032 KB |
Output isn't correct |
| 18 |
Incorrect |
278 ms |
26136 KB |
Output isn't correct |
| 19 |
Incorrect |
276 ms |
26200 KB |
Output isn't correct |
| 20 |
Incorrect |
271 ms |
26016 KB |
Output isn't correct |
