Submission #529615

#	Time	Username	Problem	Language	Result	Execution time	Memory
529615		cpp219	Zoltan (COCI16_zoltan)	C++17	140 / 140	89 ms	6992 KiB

zoltan

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 2e5 + 9;
const ll mod = 1e9 + 7;
const ll lg = 20;

ll n,m,a[N],have,ans,kq;

ll add(ll a,ll b){
    a += b;
    if (a >= mod) a -= mod; return a;
}

vector<ll> v;
void compress(){
    sort(v.begin(),v.end()); v.resize(unique(v.begin(),v.end()) - v.begin());
    for (ll i = 1;i <= n;i++)
        a[i] = lower_bound(v.begin(),v.end(),a[i]) - v.begin() + 1;
}

struct BinaryTree{
    LL bit[N];
    LL merging(LL x,LL y){
        if (x.fs == y.fs) return {x.fs,add(x.sc,y.sc)};
        return max(x,y);
    }
    void upd(ll p,LL x){
        for (ll i = p;i <= n;i += i & -i) bit[i] = merging(bit[i],x);
    }
    LL Get(ll p){
        LL res = {0,0};
        for (ll i = p;i > 0;i -= i & -i) res = merging(res,bit[i]);
        return res;
    }
};
BinaryTree icr,dcr;


int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n;
    for (ll i = 1;i <= n;i++) cin>>a[i],v.push_back(a[i]);
    compress();
    for (ll i = n;i > 0;i--){
        LL cur = icr.Get(n - a[i]),l,r;
        cur.fs++;
        if (cur.fs == 1) cur.sc = 1;
        icr.upd(n - a[i] + 1,cur); l = cur;
        cur = dcr.Get(a[i] - 1);
        cur.fs++;
        if (cur.fs == 1) cur.sc = 1;
        dcr.upd(a[i],cur); r = cur;
        if (l.fs + r.fs - 1 > ans){
            ans = l.fs + r.fs - 1;
            kq = ((long long)l.sc*r.sc) % mod;
        }
        else if (l.fs + r.fs - 1 == ans)
            kq = (kq + (long long)l.sc*r.sc)%mod;
    }
    for (ll i = 1;i <= n - ans;i++) kq = (kq * 2)%mod;
    cout<<ans<<" "<<kq;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message (stderr)

zoltan.cpp: In function 'int add(int, int)':
zoltan.cpp:17:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   17 |     if (a >= mod) a -= mod; return a;
      |     ^~
zoltan.cpp:17:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   17 |     if (a >= mod) a -= mod; return a;
      |                             ^~~~~~
zoltan.cpp: In function 'int main()':
zoltan.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140