oj.uz

Submission #548028

# Submission time Handle Problem Language Result Execution time Memory
548028 2022-04-12T08:57:42 Z FEDIKUS Zoltan (COCI16_zoltan) C++17
112 / 140
 318 ms 13388 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[4*maxn];
pii segdec[4*maxn];
pii incr[maxn];
pii decr[maxn];

int n;

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

int mul(ll a,ll b){
    return a*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(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(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 332 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 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 180 ms 12360 KB Output is correct
12 Correct 158 ms 11920 KB Output is correct
13 Correct 158 ms 7536 KB Output is correct
14 Correct 190 ms 11848 KB Output is correct
15 Correct 280 ms 12544 KB Output is correct
16 Correct 318 ms 13212 KB Output is correct
17 Incorrect 261 ms 13388 KB Output isn't correct
18 Incorrect 226 ms 13304 KB Output isn't correct
19 Incorrect 237 ms 13244 KB Output isn't correct
20 Incorrect 265 ms 13220 KB Output isn't correct