Submission #529142

#	Time	Username	Problem	Language	Result	Execution time	Memory
529142		cpp219	Zoltan (COCI16_zoltan)	C++17	21 / 140	49 ms	4520 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],kq[N],tmp[N],have;

ll bpow(ll a,ll b){
    ll res = 1;
    while(b){
        if (b & 1) res = (res*a)%mod;
        a = (a * a)%mod; b >>= 1;
    }
    return res;
}

void process(){
    fill(tmp,tmp + n + 1,mod);
    for (ll i = n;i > 0;i--){
        ll pos = lower_bound(tmp,tmp + n + 1,a[i]) - tmp;
        kq[i] += pos; tmp[pos] = a[i];
    }
}

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];
    process();
    //for (ll i = 1;i <= n;i++) cout<<kq[i]<<" "; return 0;
    for (ll i = 1;i <= n;i++) a[i] *= -1;
    process(); ll mx = 0;
    for (ll i = 1;i <= n;i++) mx = max(mx,kq[i] + 1);
    for (ll i = 1;i <= n;i++) have += ((kq[i] + 1) == mx);
    long long res = bpow(2,n - mx);
    cout<<mx<<" "<<(res*have)%mod;
}

/* 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 main()':
zoltan.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 21 / 140