oj.uz

Submission #380292

# Submission time Handle Problem Language Result Execution time Memory
380292 2021-03-20T22:34:18 Z JerryLiu06 Zoltan (COCI16_zoltan) C++11
112 / 140
 555 ms 28900 KB 
#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]; ll powr[200010]; vector<ll> 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]); }

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

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

    int MX = 0; 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;
        DP2[i] = query(decr, 1, 1, N, 1, X - 1); DP2[i].f++; if (DP2[i].s == 0) DP2[i].s = 1;
         
        update(incr, 1, 1, N, X, DP1[i]); update(decr, 1, 1, N, X, DP2[i]);
        
        MX = max(MX, DP1[i].f + DP2[i].f - 1);
    }
    ll ans = 0; for (int i = 0; i < N; i++) if (DP1[i].f + DP2[i].f - 1 == MX) { ans += DP1[i].s * DP2[i].s; ans %= MOD; }
    
    ans *= powr[N - MX]; ans %= MOD; cout << MX << " " << ans << "\n";
}

Compilation message

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
112.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 329 ms 26196 KB Output is correct
12 Correct 271 ms 24932 KB Output is correct
13 Correct 241 ms 16360 KB Output is correct
14 Correct 361 ms 25316 KB Output is correct
15 Correct 502 ms 27364 KB Output is correct
16 Correct 555 ms 28900 KB Output is correct
17 Incorrect 424 ms 25948 KB Output isn't correct
18 Incorrect 414 ms 25700 KB Output isn't correct
19 Incorrect 413 ms 25700 KB Output isn't correct
20 Incorrect 412 ms 25852 KB Output isn't correct