oj.uz

Submission #519343

# Submission time Handle Problem Language Result Execution time Memory
519343 2022-01-26T08:29:24 Z XII Zoltan (COCI16_zoltan) C++17
140 / 140
 109 ms 7016 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "COCI16_zoltan"
void Fi(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r", stdin);
        freopen(PROB".out", "w", stdout);
    }
}

const int N = 2e5 + 1;
const int MOD = 1e9 + 7;
int a[N], n;
vector<int> X;
using pi = pair<int, int>;

pi bitU[N], bitD[N];

pi comb(const pi &a, const pi &b){
    return a.fi == b.fi ? mp(a.fi, (a.se + b.se) % MOD)
                        : (a.fi > b.fi) ? a : b;
}

void updateU(int i, const pi &v){
    while(1 <= i){
        bitU[i] = comb(bitU[i], v);
        i -= i & -i;
    }
}
pi getU(int i){
    pi ans = {0, 0};
    while(i <= X.size()){
        ans = comb(ans, bitU[i]);
        i += i & -i;
    }
    return ans;
}

void updateD(int i, const pi &v){
    while(i <= X.size()){
        bitD[i] = comb(v, bitD[i]);
        i += i & -i;
    }
}
pi getD(int i){
    pi ans = {0, 0};
    while(1 <= i){
        ans = comb(bitD[i], ans);
        i -= i & -i;
    }
    return ans;
}

int mul(const int &a, const int &b){
    return (1LL * a * b) % MOD;
}

int powmod(int a, int b){
    int ans = 1;
    for(; b > 0; b >>= 1){
        if(b & 1) ans = mul(ans, a);
        a = mul(a, a);
    }
    return ans;
}

int main(){
    IOS;
    Fi();
    cin >> n;
    FORU(i, 1, n){
        cin >> a[i];
        X.eb(a[i]);
    }
    sort(ALL(X));
    X.resize(unique(ALL(X)) - X.begin());
    pi ans = {0, 0};
    FORD(i, n, 1){
        a[i] = lower_bound(ALL(X), a[i]) - X.begin() + 1;
        pi l = getD(a[i] - 1); l.fi += 1;
        l = max(l, {1, 1});
        updateD(a[i], l);
        pi r = getU(a[i] + 1); r.fi += 1;
        r = max(r, {1, 1});
        updateU(a[i], r);
        pi tmp = {l.fi + r.fi - 1, mul(l.se, r.se)};
        ans = comb(ans, tmp);
    }
    ans.se = mul(ans.se, powmod(2, n - ans.fi));
    cout << ans.fi << " " << ans.se;
    return 0;
}

Compilation message

zoltan.cpp: In function 'pi getU(int)':
zoltan.cpp:46:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     while(i <= X.size()){
      |           ~~^~~~~~~~~~~
zoltan.cpp: In function 'void updateD(int, const pi&)':
zoltan.cpp:54:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     while(i <= X.size()){
      |           ~~^~~~~~~~~~~
zoltan.cpp: In function 'void Fi()':
zoltan.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 59 ms 5280 KB Output is correct
12 Correct 53 ms 4708 KB Output is correct
13 Correct 46 ms 4384 KB Output is correct
14 Correct 73 ms 5000 KB Output is correct
15 Correct 88 ms 6060 KB Output is correct
16 Correct 109 ms 7016 KB Output is correct
17 Correct 74 ms 5784 KB Output is correct
18 Correct 83 ms 5824 KB Output is correct
19 Correct 73 ms 5840 KB Output is correct
20 Correct 68 ms 5848 KB Output is correct