Submission #883708

#	Time	Username	Problem	Language	Result	Execution time	Memory
883708		vjudge1	Zoltan (COCI16_zoltan)	C++17	42 / 140	117 ms	31548 KiB

zoltan

#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
#define int long long
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define inf 1000000009
#define MOD 998244353
#define lim 200005
using namespace std;


int add(int x, int y){
    if(x+y>=MOD) return x+y-MOD;
    return x+y;
}

int mult(int x, int y){
    return ((x%MOD) * (y%MOD))%MOD;
}

int exp(int b, int t){
    int res = 1;
    while(t>0){
        if(t%2){
            t--;
            res *=b;
            res%=MOD;
            continue;
        }
        t/=2;
        b*=b;
        b%=MOD;
    }
    return res;
}


void solve(){
    int n; cin >> n;
    int arr[n+1];
    for(int i=1; i<=n; i++) cin >> arr[i];
    vi inc(1, 0), dec(1, inf);
    vector<vi> past1 = {{inf}}, past2 = {{0}};
    vector<vi> pref1 = {{1}}, pref2 = {{1}};
    ii ans[n+1];
    int maxi=0;

    for(int i=n; i>=1; i--){
        //cerr << "---" spc i spc "---" << endl;

        int pos = lower_bound(all(inc), arr[i]) - inc.begin();
        if(pos == inc.size()){
            inc.pb(arr[i]);
            vi v = {inf};
            vi vv = {0};
            past1.pb(v);
            pref1.pb(vv);
        }
        else{
            inc[pos] = arr[i];
        }
        past1[pos].pb(arr[i]);

        int aft1 = lower_bound(all(past1[pos-1]), arr[i], greater<int>()) - past1[pos-1].begin();
        //for(auto j:past1[pos-1]) cerr << j << endl;
        //cerr << aft1 << endl;
        int cnt1 = pref1[pos-1].back();
        if(aft1>1) cnt1 -= (pref1[pos-1][aft1-1]);
        if(cnt1<0) cnt1+=MOD;
        pref1[pos].pb(add(pref1[pos].back(), cnt1));



        int pos2 = lower_bound(all(dec), arr[i], greater<int>()) - dec.begin();
        if(pos2 == dec.size()){
            dec.pb(arr[i]);
            vi vv = {0};
            past2.pb(vv);
            pref2.pb(vv);
        }
        else{
            dec[pos2] = arr[i];
        }
        past2[pos2].pb(arr[i]);

        int aft2 = lower_bound(all(past2[pos2-1]), arr[i]) - past2[pos2-1].begin();
        //cerr << "here" << endl;
        //for(auto j:past2[pos2-1]) cerr << j << endl;
        //cerr << aft2 << endl;
        int cnt2 = pref2[pos2-1].back();
        if(aft2>1) cnt2 -= (pref2[pos2-1][aft2-1]);
        if(cnt2<0) cnt2+=MOD;
        pref2[pos2].pb(add(pref2[pos2].back(), cnt2));



        ans[i].st = pos + pos2 -1;
        ans[i].nd = mult(cnt1, cnt2);
        maxi = max(maxi, ans[i].st);
        //cerr << cnt1 spc cnt2 << endl;
        //cerr << "wowsies" spc ans[i].st spc ans[i].nd << endl;
    }

    int tot=0;
    for(int i=1; i<=n; i++) if(ans[i].st == maxi) tot = add(tot, ans[i].nd);
    cout << maxi spc mult(tot, exp(2, n-maxi)) << endl;
}



signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    #ifdef Local
    freopen("in","r",stdin);
    freopen("out","w",stdout);
    #endif

    /*freopen("fcolor.in","r",stdin);
    freopen("fcolor.out","w",stdout);*/

    int t=1;
    //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

zoltan.cpp: In function 'void solve()':
zoltan.cpp:60:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         if(pos == inc.size()){
      |            ~~~~^~~~~~~~~~~~~
zoltan.cpp:83:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         if(pos2 == dec.size()){
      |            ~~~~~^~~~~~~~~~~~~

• Subtask 1: 42 / 140