oj.uz

답안 #380304

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
380304 2021-03-20T23:08:12 Z JerryLiu06 Zoltan (COCI16_zoltan) C++11
140 / 140
 546 ms 27168 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] = comb(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] = comb(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] = comb(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
140.0 / 140.0

# 결과 실행 시간 메모리 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 0 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 330 ms 25060 KB Output is correct
12 Correct 274 ms 24036 KB Output is correct
13 Correct 260 ms 15336 KB Output is correct
14 Correct 384 ms 24036 KB Output is correct
15 Correct 523 ms 25572 KB Output is correct
16 Correct 546 ms 27168 KB Output is correct
17 Correct 420 ms 24548 KB Output is correct
18 Correct 417 ms 24548 KB Output is correct
19 Correct 435 ms 24548 KB Output is correct
20 Correct 417 ms 24420 KB Output is correct