oj.uz

Submission #742815

# Submission time Handle Problem Language Result Execution time Memory
742815 2023-05-17T02:54:15 Z Trent Zoltan (COCI16_zoltan) C++17
112 / 140
 293 ms 16156 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;}

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
112.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 304 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Incorrect 2 ms 340 KB Output isn't correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 243 ms 12584 KB Output is correct
12 Correct 152 ms 10976 KB Output is correct
13 Correct 135 ms 10348 KB Output is correct
14 Incorrect 203 ms 11308 KB Output isn't correct
15 Incorrect 238 ms 13924 KB Output isn't correct
16 Incorrect 293 ms 16156 KB Output isn't correct
17 Correct 217 ms 15552 KB Output is correct
18 Correct 230 ms 15712 KB Output is correct
19 Correct 216 ms 15620 KB Output is correct
20 Correct 218 ms 15552 KB Output is correct