oj.uz

Submission #548042

# Submission time Handle Problem Language Result Execution time Memory
548042 2022-04-12T09:33:10 Z FEDIKUS Zoltan (COCI16_zoltan) C++17
112 / 140
 322 ms 13552 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(int (i)=s;(i)<(f);(i)++)
#define fb(i,s,f) for(int (i)=s-1;(i)>=f;(i)--)
#define ffi(i,s,f) for(int (i)=s;(i)<=(f);(i)++)
#define fbi(i,s,f) for(int (i)=s;(i)>=(f);(i)--)
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#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<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;

const int maxn=2e5+10;
const int mod=1e9+7;

int niz[maxn];
int compr[maxn];
pii seginc[5*maxn];
pii segdec[5*maxn];
pii incr[maxn];
pii decr[maxn];

int n;

int add(int a,int b){
    return (a+b)%mod;
}

int mul(int a,int b){
    return ll(a)*ll(b)%mod;
}

int pwr(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=mul(ret,a);
        b/=2;
        a=mul(a,a);
    }
    return ret;
}

pii comb(pii a,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(int t,pii v,pii *seg,int ind=1,int l=0,int r=n-1){
    if(l==r){
        seg[ind]=v;
        return;
    }
    int 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(int tl,int tr,pii *seg,int ind=1,int l=0,int r=n-1){
    if(tl<=l && r<=tr) return seg[ind];
    int 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(1,1));
            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(1,1));
            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;
    int t=1;
//    cin>>t;
    while(t--) solve();
    return 0;
}

Compilation message

zoltan.cpp: In function 'void solve()':
zoltan.cpp:9:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define ff(i,s,f) for(int (i)=s;(i)<(f);(i)++)
      |                           ^
zoltan.cpp:89:5: note: in expansion of macro 'ff'
   89 |     ff(i,0,n){
      |     ^~
zoltan.cpp:9:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define ff(i,s,f) for(int (i)=s;(i)<(f);(i)++)
      |                           ^
zoltan.cpp:94:5: note: in expansion of macro 'ff'
   94 |     ff(i,0,n){
      |     ^~
zoltan.cpp:10:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fb(i,s,f) for(int (i)=s-1;(i)>=f;(i)--)
      |                           ^
zoltan.cpp:97:5: note: in expansion of macro 'fb'
   97 |     fb(i,n,0){
      |     ^~
zoltan.cpp:9:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define ff(i,s,f) for(int (i)=s;(i)<(f);(i)++)
      |                           ^
zoltan.cpp:118:5: note: in expansion of macro 'ff'
  118 |     ff(i,0,n){
      |     ^~

Subtask #1
112.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 178 ms 12492 KB Output is correct
12 Correct 199 ms 11976 KB Output is correct
13 Correct 154 ms 7756 KB Output is correct
14 Correct 179 ms 12100 KB Output is correct
15 Correct 272 ms 12868 KB Output is correct
16 Correct 322 ms 13472 KB Output is correct
17 Incorrect 248 ms 13484 KB Output isn't correct
18 Incorrect 259 ms 13548 KB Output isn't correct
19 Incorrect 233 ms 13552 KB Output isn't correct
20 Incorrect 240 ms 13480 KB Output isn't correct