oj.uz

Submission #780240

# Submission time Handle Problem Language Result Execution time Memory
780240 2023-07-12T07:37:13 Z chanhchuong123 Zoltan (COCI16_zoltan) C++14
140 / 140
 95 ms 7744 KB 
#include <bits/stdc++.h>
using namespace std;
#define task ""
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define BIT(mask, i) ((mask) >> (i) & 1)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (b), _a = (a); i >= _a; --i)

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

const int dx[] = {-1, 0, 0, +1};
const int dy[] = {0, -1, +1, 0};

const int MOD = 1e9 + 7;
const int MAX = 200200;
int n;
int a[MAX];
int pw[MAX];
vector<int> tmp;

pair<int, int> combine(const pair<int, int> &u, const pair<int, int> &v) {
    if (u.fi > v.fi) return u;
    if (u.fi < v.fi) return v;
    return make_pair(u.fi, (u.se + v.se) % MOD);
}

pair<int, int> f[MAX], g[MAX];
void update(pair<int, int> bit[], int id, const pair<int, int> &value) {
    for (; id <= n; id += id & -id) bit[id] = combine(bit[id], value);
}
pair<int, int> get(pair<int, int> bit[], int id) {
    pair<int, int> res(0, 1);
    for (; id > 0; id -= id & -id) res = combine(res, bit[id]);
    ++res.fi;     return res;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}


    cin >> n;
    pw[0] = 1;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        tmp.push_back(a[i]);
        pw[i] = 2LL * pw[i - 1] % MOD;
    }
    sort(all(tmp));
    tmp.resize(unique(all(tmp)) - tmp.begin());

    int ans = 0, cnt = 0;
    for (int i = n; i >= 1; --i) {
        a[i] = upper_bound(all(tmp), a[i]) - tmp.begin();
        pair<int, int> inc = get(f, a[i] - 1);
        pair<int, int> dec = get(g, n - a[i]);
        int len = inc.fi + dec.fi - 1;
        if (len > ans) {
            ans = len;
            cnt = 1LL * inc.se * dec.se % MOD;
        } else if (len == ans) {
            cnt = (cnt + 1LL * inc.se * dec.se % MOD) % MOD;
        }
        update(f, a[i], inc);
        update(g, n - a[i] + 1, dec);
    }
    cout << ans << ' ' << 1LL * cnt * pw[n - ans] % MOD;

	return 0;
}

Compilation message

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

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 54 ms 5956 KB Output is correct
12 Correct 46 ms 5260 KB Output is correct
13 Correct 42 ms 4900 KB Output is correct
14 Correct 68 ms 5584 KB Output is correct
15 Correct 83 ms 6696 KB Output is correct
16 Correct 95 ms 7744 KB Output is correct
17 Correct 65 ms 6600 KB Output is correct
18 Correct 64 ms 6640 KB Output is correct
19 Correct 62 ms 6652 KB Output is correct
20 Correct 63 ms 6608 KB Output is correct