oj.uz

Submission #742816

# Submission time Handle Problem Language Result Execution time Memory
742816 2023-05-17T02:55:04 Z Trent Zoltan (COCI16_zoltan) C++17
140 / 140
 292 ms 25312 KB 
#include "bits/stdc++.h"
 
using namespace std;
#define forR(i, a) for(int i = 0; (i) < (a); ++(i))
#define REP(i, a, b) for(int i = (a); (i) < (b); ++i)
#define all(a) a.begin(), a.end()
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define printArr(arr) for(int asdfg : arr) cout << asdfg << ' '; cout << '\n'
#define open(x) freopen(((string) x + ".in").c_str(), "r", stdin); freopen(((string) x + ".out").c_str(), "w", stdout);
typedef long long ll;
typedef long double ld;
struct pii{ll a, b;};
struct tii{ll a, b, c;};
bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}
#define int ll

const int MN = 2e5 + 10, ME = 4 * MN, MOD = 1e9+7;

const ll po(int b, int e){
    if(e == 0) return 1;
    else {
        ll h = po(b, e / 2);
        return e % 2 == 0 ? h * h % MOD : h * h % MOD * b % MOD;
    }
}
struct node{int v, c;};
node comb(const node l, const node r){
    node ret = {max(l.v, r.v), 0};
    if(l.v == ret.v) ret.c += l.c;
    if(r.v == ret.v) ret.c += r.c;
    ret.c %= MOD;
    return ret;
}
struct Seg{
    node seg[ME];
    void init(int n){
        REP(i, 1, 4 * n + 1) seg[i] = {0, 0};
    }
    void upd(int i, int val, int cnt, int v, int nl, int nr){
        if(nl == nr) seg[v] = {val, cnt};
        else {
            int mid = (nl+nr)/2;
            if(i <= mid) upd(i, val, cnt, 2*v, nl, mid);
            else upd(i, val, cnt, 2*v+1, mid+1, nr);
            seg[v] = comb(seg[2*v], seg[2*v+1]);
        }
    }
    node qu(int l, int r, int v, int nl, int nr){
        if(l > r) return {0, 0};
        else if(nl == l && nr == r) return seg[v];
        else {
            int mid = (nl+nr)/2;
            return comb(
                qu(l, min(mid, r), 2*v, nl, mid),
                qu(max(mid+1,l), r, 2*v+1, mid+1, nr)
            );
        }
    }
} seg;

void solve(int n, int v[MN], int id[MN], node ans[MN]){
    seg.init(n);
    vector<tii> upd;
    REP(i, 1, n + 1) {
        ans[i] = comb(seg.qu(id[i]+1, n, 1, 1, n), {0, 1});
        ans[i].v += 1;
        upd.push_back({id[i], ans[i].v, ans[i].c});
        if(v[i] == n || v[i] != v[i+1]){
            for(auto [ind, len, cnt] : upd) seg.upd(ind, len, cnt, 1, 1, n);
            upd.clear();
        }
    }
    // cout << '\n';
    // REP(i, 1, n + 1) printf("%d ", v[i]); cout << '\n';
    // REP(i, 1, n + 1) printf("%d ", id[i]); cout << '\n';
    // REP(i, 1, n + 1) printf("[%d %d] ", ans[i].v, ans[i].c); cout << '\n';
}

int v[MN], id[MN];
node a1[MN], a2[MN];
pii arr[MN];
signed main(){
    int n; cin >> n;
    REP(i, 1, n+1) {
        cin >> arr[i].b;
        arr[i].a = i;
    }
    sort(arr+1, arr+n+1, [](pii a, pii b){return a.b < b.b;});
    REP(i, 1, n + 1) v[i]=arr[i].b, id[i]=arr[i].a;
    solve(n, v, id, a1);
    reverse(v+1,v+1+n); reverse(id+1,id+n+1);
    solve(n, v, id, a2);
    node bes = {0, 0};
    REP(i, 1, n + 1) bes = comb(bes, {a1[i].v + a2[n+1-i].v - 1, a1[i].c * a2[n+1-i].c});
    cout << bes.v << ' ' << bes.c * po(2, n-bes.v) % MOD << '\n';
}

Compilation message

zoltan.cpp: In function 'bool operator<(pii, pii)':
zoltan.cpp:14:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   14 | bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}
      |                                                    ~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 177 ms 20096 KB Output is correct
12 Correct 152 ms 17456 KB Output is correct
13 Correct 138 ms 16468 KB Output is correct
14 Correct 188 ms 17544 KB Output is correct
15 Correct 283 ms 21760 KB Output is correct
16 Correct 292 ms 25084 KB Output is correct
17 Correct 221 ms 25292 KB Output is correct
18 Correct 266 ms 25296 KB Output is correct
19 Correct 227 ms 25292 KB Output is correct
20 Correct 238 ms 25312 KB Output is correct