Submission #742815

#	Time	Username	Problem	Language	Result	Execution time	Memory
742815		Trent	Zoltan (COCI16_zoltan)	C++17	112 / 140	293 ms	16156 KiB

zoltan

#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 (stderr)

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 / 140