oj.uz

Submission #548022

# Submission time Handle Problem Language Result Execution time Memory
548022 2022-04-12T08:48:59 Z FEDIKUS Zoltan (COCI16_zoltan) C++17
70 / 140
 295 ms 13772 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,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+=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
70.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 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 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 Incorrect 172 ms 12680 KB Output isn't correct
12 Incorrect 154 ms 12168 KB Output isn't correct
13 Incorrect 137 ms 7904 KB Output isn't correct
14 Incorrect 186 ms 12200 KB Output isn't correct
15 Incorrect 236 ms 12976 KB Output isn't correct
16 Incorrect 295 ms 13764 KB Output isn't correct
17 Incorrect 236 ms 13576 KB Output isn't correct
18 Incorrect 226 ms 13696 KB Output isn't correct
19 Incorrect 235 ms 13772 KB Output isn't correct
20 Incorrect 233 ms 13568 KB Output isn't correct