oj.uz

답안 #243507

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243507 2020-07-01T09:19:20 Z ne4eHbKa Zoltan (COCI16_zoltan) C++17
140 / 140
 127 ms 7480 KB 
//{ <defines>
#include <bits/stdc++.h>
using namespace std;

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,-O3")

#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)

#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _  << ' ' <<

#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back

#define sz(x) int((x).size())
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset((x), (y), sizeof (x))

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef ve<int> vi;

inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());

template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}

int md = 998244353;

inline int m_add(int&a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_sum(int a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_mul(int&a, int b) {re a = 1ll * a * b % md;}
inline int m_prod(int a, int b) {re 1ll * a * b % md;}

int m_bpow(ll A, ll b) {
    int a = A % md;
    ll ans = 1;
    for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
        (ans *= ans) %= md;
        if(p & b)
            (ans *= a) %= md;
    }
    re ans;
}

//const ld pi = arg(complex<ld>(-1, 0));
//const ld pi2 = pi + pi;
const int oo = 2e9;
const ll OO = 4e18;
//} </defines>
const int N = 2e5 + 5;

int n, m;
int a[N], p2[N];
pii le[N], gr[N];

inline void upd(pii &a, const pii &b) {
    if(b.ft >= a.ft) {
        if(b.ft == a.ft) {
            a.sd += b.sd;
            if(a.sd >= md) a.sd -= md;
        } else {
            a = b;
        }
    }
}

pii f[N];

void fupd(int i, pii v) { for(i++; i < N; i += i & -i) upd(f[i], v); }
pii fget(int i) { pii v {0, 0}; for(; i; i -= i & -i) upd(v, f[i]); re v; }

void count(pii *v) {
    clr(f, 0);
    for(int i = 0; i < n; ++i) {
        v[i] = {0, 1};
        upd(v[i], fget(a[i]));
        v[i].ft++;
        fupd(a[i], v[i]);
    }
}

void solve() {
    md = 1e9 + 7;
    for(int i = 0; i < N; ++i) p2[i] = !i ? 1 : m_sum(p2[i - 1], p2[i - 1]);
    cin >> n;
    fo(n) cin >> a[n - 1 - i];
    int *b = (int*) memcpy(malloc(n << 2), a, n << 2);
    sort(b, b + n);
    m = unique(b, b + n) - b;
    for(int i = 0; i < n; ++i) {
        a[i] = lower_bound(b, b + m, a[i]) - b + 1;
    }
    count(le);
    fo(n) a[i] = m + 1 - a[i];
    count(gr);
    int M = 1;
    fo(n) umax(M, le[i].ft + gr[i].ft - 1);
    int ans = 0;
    for(int i = 0; i < n; ++i) {
        if(le[i].ft + gr[i].ft < M + 1) continue;
        m_add(ans, m_prod(p2[n - M], m_prod(le[i].sd, gr[i].sd)));
    }
    cout << M _ ans << endl;
}

int main() {
    cout.precision(15); cout << fixed;
    cerr.precision(15); cerr << fixed;
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
    int tests; cin >> tests;
    for(int test = 1; test <= tests; ++test) {
		cerr << "case #" << test << endl;
        solve();
        cerr << endl;
    }
#else
//    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
#endif
    return 0;
}

Compilation message

zoltan.cpp: In function 'int m_bpow(ll, ll)':
zoltan.cpp:50:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
                       ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 7 ms 2688 KB Output is correct
3 Correct 7 ms 2688 KB Output is correct
4 Correct 7 ms 2688 KB Output is correct
5 Correct 7 ms 2688 KB Output is correct
6 Correct 7 ms 2688 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2688 KB Output is correct
9 Correct 7 ms 2688 KB Output is correct
10 Correct 7 ms 2688 KB Output is correct
11 Correct 78 ms 6396 KB Output is correct
12 Correct 67 ms 6012 KB Output is correct
13 Correct 66 ms 5752 KB Output is correct
14 Correct 89 ms 6008 KB Output is correct
15 Correct 114 ms 6776 KB Output is correct
16 Correct 127 ms 7416 KB Output is correct
17 Correct 91 ms 7416 KB Output is correct
18 Correct 87 ms 7416 KB Output is correct
19 Correct 85 ms 7416 KB Output is correct
20 Correct 92 ms 7480 KB Output is correct