oj.uz

Submission #548043

# Submission time Handle Problem Language Result Execution time Memory
548043 2022-04-12T09:38:22 Z FEDIKUS Zoltan (COCI16_zoltan) C++17
112 / 140
 285 ms 13256 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=1e6+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(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 0 ms 340 KB Output is correct
3 Correct 1 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 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 175 ms 12236 KB Output is correct
12 Correct 156 ms 11780 KB Output is correct
13 Correct 137 ms 7480 KB Output is correct
14 Correct 184 ms 11692 KB Output is correct
15 Correct 242 ms 12596 KB Output is correct
16 Correct 285 ms 13132 KB Output is correct
17 Incorrect 222 ms 13160 KB Output isn't correct
18 Incorrect 241 ms 13168 KB Output isn't correct
19 Incorrect 226 ms 13164 KB Output isn't correct
20 Incorrect 230 ms 13256 KB Output isn't correct