Submission #988961

#	Time	Username	Problem	Language	Result	Execution time	Memory
988961		Celebi_276	Zoltan (COCI16_zoltan)	C++17	140 / 140	111 ms	10068 KiB

zoltan

#include <bits/stdc++.h>

using namespace std;

#define     exetime    cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"
#define   ynifnl(c)    cout << ((c) ? "YES\n" : "NO\n")
#define     ynif(c)    cout << ((c) ? "YES" : "NO")
#define        TASK    "TEST"
#define        lint    long long int
#define       ulint    unsigned lint
#define       sz(v)    (int(v.size()))
#define      all(v)    v.begin(), v.end()
#define     rall(v)    v.rbegin(), v.rend()
#define          fi    first 
#define          se    second
#define     bit1(x)    __builtin_popcountll(x)
#define coutf(f, d)    cout << fixed << setprecision(d) << f

typedef pair <int, int> pii;
const int N = 2E5 + 25, MOD = 1E9 + 7;
int n, a[N], b[N];
pii R({0, 1}), G, lis[N], lds[N];

int mul (int a, int b) {
    int T = 0;
    for (; b; (a += a) %= MOD, b >>= 1) if (b & 1) (T += a) %= MOD;
    return T;
}
int pw2 (int a) {
    int T = 1;
    for (; a; --a, (T *= 2) %= MOD);
    return T;
}
void update_ (pii &A, pii B) {
    if (A.fi < B.fi) A = B;
    else if (A.fi == B.fi) (A.se += B.se) %= MOD;
}

namespace Fenwick_Tree {
    pii BIT[2][N];
    void update (bool t, int x, pii v) {
        if (!t) for (; x <= n; update_(BIT[t][x], v), x += x & -x);
        else for (; x; update_(BIT[t][x], v), x -= x & -x);
    }
    pii get (bool t, int x) {
        pii g = {0, 1};
        if (!t) for (; x; update_(g, BIT[t][x]), x -= x & -x);
        else for (; x <= n; update_(g, BIT[t][x]), x += x & -x);
        return g;
    }
}
using namespace Fenwick_Tree;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    if (fopen(TASK".INP", "r")) {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
    for (int i = n; i; --i) {
        lis[i] = get(1, a[i] + 1);
        lds[i] = get(0, a[i] - 1);
        lis[i].fi++;
        lds[i].fi++;
        G.fi = lis[i].fi + lds[i].fi - 1;
        G.se = mul(lis[i].se, lds[i].se);
        update_(R, G);
        update(1, a[i], lis[i]); update(0, a[i], lds[i]);
    }
    cout << R.fi << " " << mul(pw2(n - R.fi), R.se);
    return exetime, 0;
}

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140