Submission #519300

#	Time	Username	Problem	Language	Result	Execution time	Memory
519300		XII	Zoltan (COCI16_zoltan)	C++17	56 / 140	82 ms	5452 KiB

zoltan

#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());
    FORU(i, 1, n){
        a[i] = lower_bound(ALL(X), a[i]) - X.begin() + 1;
        if(a[i] <= a[1]){
            pi tmp = getU(a[i] + 1); tmp.fi += 1;
            tmp = comb(tmp, {1, 1});
            updateU(a[i], tmp);
        } else{
            pi tmp = getD(a[i] - 1); tmp.fi += 1;
            tmp = comb(tmp, {1, 1});
            updateD(a[i], tmp);
        }
    }
    pi lef = comb({0, 1}, getU(1));
    pi rig = comb({0, 1}, getD(X.size()));
    pi ans = {lef.fi + rig.fi, mul(lef.se, rig.se)};
    ans.se = mul(ans.se, powmod(2, n - ans.fi));
    cout << ans.fi << " " << ans.se;
    return 0;
}

Compilation message (stderr)

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: 56 / 140