Submission #1176489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176489		InvMOD	Zoltan (COCI16_zoltan)	C++20	140 / 140	70 ms	6588 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REV(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 2e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;


int add(int x, int y){
    return (x + y < MOD ? x + y : x + y - MOD);
}

int mul(int x, int y){
    return (1ll * x * y) % MOD;
}

int bpow(int x, int y){
    int ans = 1;
    while(y){
        if(y & 1) ans = mul(ans, x);
        x = mul(x, x);
        y >>= 1;
    }
    return ans;
}

struct Node{
    int Mx, cnt;
    Node(int Mx = 0, int cnt = 0): Mx(Mx), cnt(cnt) {}

    friend const Node operator + (const Node& a, const Node &b){
        if(a.Mx == b.Mx)
            return Node(a.Mx, add(a.cnt, b.cnt));
        return (a.Mx < b.Mx ? b : a);
    }
};
struct BIT{
    vector<Node> bit;
    BIT(int n = 0): bit(n + 1) {}

    void update(int p, int Mx, int cnt){
        Node v = Node(Mx, cnt);
        for(; p < sz(bit); p += (p & (-p))){
            bit[p] = bit[p] + v;
        }
    }

    Node query(int p){
        Node ans = Node();
        for(; p > 0; p -= (p & (-p))){
            ans = ans + bit[p];
        }
        return ans;
    }

    void reset(){
        for(int i = 1; i < sz(bit); i++){
            bit[i] = Node();
        }
    }
};


void solve()
{
    int n; cin >> n;

    vector<int> a(n + 1), comp;
    FOR(i, 1, n){
        cin >> a[i];
        comp.pb(a[i]);
    }

    sort(all(comp)), compact(comp);
    FOR(i, 1, n)
        a[i] = lower_bound(all(comp), a[i]) - comp.begin() + 1;

    /*
        Each position i will be a "corner"
        longest increasing sub will go from n -> i -> n again
        so we will calculate a prefix longest increasing sub and a longest decreasing sub from n -> i
    */

    vector<Node> lis(n + 1), lds(n + 1); BIT bit(sz(comp));

    for(int i = n; i >= 1; i--){
        lis[i] = bit.query(a[i] - 1);

        lis[i].Mx++, lis[i].cnt = max(lis[i].cnt, 1);
        bit.update(a[i], lis[i].Mx, lis[i].cnt);
    }
    bit.reset();

    for(int i = n; i >= 1; i--){
        int new_ai = sz(comp) - a[i] + 1;
        lds[i] = bit.query(new_ai - 1);

        lds[i].Mx++, lds[i].cnt = max(lds[i].cnt, 1);
        bit.update(new_ai, lds[i].Mx, lds[i].cnt);
    }

    Node ans = Node();
    for(int i = 1; i <= n; i++){
        ans = ans + Node(lis[i].Mx + lds[i].Mx - 1, mul(lds[i].cnt, lis[i].cnt));
    }

    cout << ans.Mx <<" " << mul(ans.cnt, bpow(2, n - ans.Mx)) << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140