Submission #1125924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125924		SoMotThanhXuan	Zoltan (COCI16_zoltan)	C++20	140 / 140	93 ms	9056 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define mp make_pair
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
inline bool maximize(int &u, int v){
    if(v > u){
        u = v;
        return true;
    }
    return false;
}
inline bool minimize(int &u, int v){
    if(v < u){
        u = v;
        return true;
    }
    return false;
}
inline bool maximizell(long long &u, long long v){
    if(v > u){
        u = v;
        return true;
    }
    return false;
}
inline bool minimizell(long long &u, long long v){
    if(v < u){
        u = v;
        return true;
    }
    return false;
}
const int mod = 1e9 + 7;
inline int fastPow(int a, int n){
    int res = 1;
    while(n){
        if(n & 1)res = 1ll * res * a * mod;
        a = 1ll * a * a % mod;
        n >>= 1;
    }
    return res;
}
inline void add(int &u, int v){
    u += v;
    if(u >= mod) u -= mod;
}
inline void sub(int &u, int v){
    u -= v;
    if(u < 0) u += mod;
}
const int maxN = 2e5 + 5;
const int inf = 2e9;
const long long infll = 1e18;
int power[maxN], n, a[maxN], comp[maxN];

struct Node{
    int len, cnt;
    Node(int lenVal = 0, int cntVal = 0){
        len = lenVal;
        cnt = cntVal;
    }
    Node operator + (const Node &rhs) const {
        if(len > rhs.len) return *this;
        if(rhs.len > len) return rhs;
        Node res = *this;
        add(res.cnt, rhs.cnt);
        return res;
    }
};
Node f[maxN], g[maxN];
#define dec DECCCCC
Node inc[maxN], dec[maxN];
void updateInc(int x, Node val){
    for(; x <= n; x += x & -x)inc[x] = inc[x] + val;
}
Node getInc(int x){
    Node res;
    for(; x >= 1; x &= x - 1)res = res + inc[x];
    return res;
}
void updateDec(int x, Node val){
    for(; x >= 1; x &= x - 1)dec[x] = dec[x] + val;
}
Node getDec(int x){
    Node res;
    for(; x <= n; x += x & -x)res = res + dec[x];
    return res;
}

void process(){
    cin >> n;
    power[0] = 1;
    FOR(i, 1, n){
        cin >> a[i];
        power[i] = 2ll * power[i - 1] % mod;
        comp[i] = a[i];
    }
    sort(comp + 1, comp + 1 + n);
    FOR(i, 1, n){
        a[i] = lower_bound(comp + 1, comp + 1 + n, a[i]) - comp;
    }
    REP(i, n, 1){
        Node val = getInc(a[i] - 1);
        if(val.len == 0)f[i] = Node(1, 1);
        else f[i] = val, ++f[i].len;
        updateInc(a[i], f[i]);
        val = getDec(a[i] + 1);
        if(val.len == 0)g[i] = Node(1, 1);
        else g[i] = val, ++g[i].len;
        updateDec(a[i], g[i]);
    }
    Node res;
    FOR(i, 1, n){
        Node Merge;
        Merge.len = f[i].len + g[i].len - 1;
        Merge.cnt = 1ll * f[i].cnt * g[i].cnt % mod * power[n - Merge.len] % mod;
        res = res + Merge;
    }
    cout << res.len << ' ' << res.cnt;
}
#define NAME "Zoltan"
int main(){
    if(fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
//    cin >> t;
    while(t--)
        process();
//    cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" ;
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 140 / 140