Submission #379991

#	Time	Username	Problem	Language	Result	Execution time	Memory
379991		JerryLiu06	Zoltan (COCI16_zoltan)	C++11	56 / 140	416 ms	27496 KiB

zoltan

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, ll> pii;

#define pb push_back

#define f first
#define s second

int N, A[200010], MX = 0; ll ans = 0; ll powr[100010]; vector<int> allX;

pii incr[800010]; pii decr[800010]; pii DP1[200010], DP2[200010];

const ll MOD = 1000000007LL;

int getX(int X) { return lower_bound(allX.begin(), allX.end(), X) - allX.begin() + 1; }

pii comb(pii A, pii B) { if (A.f != B.f) return max(A, B); return pii {A.f, (A.s + B.s) % MOD}; }

void update(pii tree[], int x, int l, int r, int pos, pii val) { int mid = (l + r) / 2;
    if (r < pos || l > pos) return ; if (l == r) { tree[x] = val; return ; }

    update(tree, 2 * x, l, mid, pos, val); update(tree, 2 * x + 1, mid + 1, r, pos, val);

    tree[x] = comb(tree[2 * x], tree[2 * x + 1]);
}
pii query(pii tree[], int x, int l, int r, int tl, int tr) { int mid = (l + r) / 2;
    if (r < tl || l > tr) return pii {0, 0}; if (tl <= l && r <= tr) return tree[x];

    return comb(query(tree, 2 * x, l, mid, tl, tr), query(tree, 2 * x + 1, mid + 1, r, tl, tr));
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    
    cin >> N; for (int i = 0; i < N; i++) { cin >> A[i]; allX.pb(A[i]); }

    powr[0] = 1; for (int i = 1; i <= N; i++) powr[i] = (2 * powr[i - 1]) % MOD;

    sort(allX.begin(), allX.end()); allX.resize(distance(allX.begin(), unique(allX.begin(), allX.end())));

    for (int i = N - 1; i >= 0; i--) { int X = getX(A[i]);
        DP1[i] = query(incr, 1, 1, N, X + 1, N); DP1[i].f++; if (DP1[i].s == 0) DP1[i].s = 1;

        update(incr, 1, 1, N, X, DP1[i]);
    }
    for (int i = N - 1; i >= 0; i--) { int X = getX(A[i]);
        DP2[i] = query(decr, 1, 1, N, 1, X - 1); DP2[i].f++; if (DP2[i].s == 0) DP2[i].s = 1;

        MX = max(MX, DP1[i].f + DP2[i].f - 1);

        update(decr, 1, 1, N, X, DP2[i]);
    }
    for (int i = 0; i < N; i++) if (DP1[i].f + DP2[i].f - 1 == MX) {
        ll prod = (DP1[i].s * DP2[i].s) % MOD;
        
        ans += (prod * powr[N - DP1[i].f - DP2[i].f + 1]) % MOD;
    }
    cout << MX << " " << ans << endl;
}

Compilation message (stderr)

zoltan.cpp: In function 'void update(pii*, int, int, int, int, pii)':
zoltan.cpp:24:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   24 |     if (r < pos || l > pos) return ; if (l == r) { tree[x] = val; return ; }
      |     ^~
zoltan.cpp:24:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   24 |     if (r < pos || l > pos) return ; if (l == r) { tree[x] = val; return ; }
      |                                      ^~
zoltan.cpp: In function 'pii query(pii*, int, int, int, int, int)':
zoltan.cpp:31:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   31 |     if (r < tl || l > tr) return pii {0, 0}; if (tl <= l && r <= tr) return tree[x];
      |     ^~
zoltan.cpp:31:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   31 |     if (r < tl || l > tr) return pii {0, 0}; if (tl <= l && r <= tr) return tree[x];
      |                                              ^~

• Subtask 1: 56 / 140