Submission #1211665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211665		vanea	Zoltan (COCI16_zoltan)	C++20	7 / 140	166 ms	20124 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mxN = 1e6+10;
const int MOD = 1e9+7;
const int INF = 1e9+10;

array<array<int, 2>, 2> st[mxN];
array<array<int, 2>, 2> lazy[mxN];
vector<int> values;

int val(int x) {
    return lower_bound(values.begin(), values.end(), x) - values.begin();
}

array<int, 2> comb(array<int, 2> a, array<int, 2> b) {
    array<int, 2> ans = {0, 0};
    int x = 0, y = 1;
    if(a[x] == b[x]) {
        ans[x] = a[x];
        ans[y] = (a[y]+b[y]) % MOD;
    }
    else if(a[x] > b[x]) {
        ans[x] = a[x];
        ans[y] = a[y];
    }
    else {
        ans[x] = b[x];
        ans[y] = b[y];
    }
    return ans;
}

void push(int node, int l, int r, int flag) {
    if(lazy[node][flag][1] == 0) return ;
    if(lazy[node][flag][0] == 1) {
        lazy[node*2][flag] = {1, 1};
        lazy[node*2+1][flag] = {1, 1};
        st[node*2][flag][0]++;
        st[node*2][flag][1] = 1;
        st[node*2+1][flag][0]++;
        st[node*2+1][flag][1] = 1;
    }
    else {
        lazy[node*2][flag][1] += lazy[node][flag][1];
        lazy[node*2][flag][1] %= MOD;
        lazy[node*2+1][flag][1] += lazy[node][flag][1];
        lazy[node*2+1][flag][1] %= MOD;
        st[node*2][flag][1] += lazy[node][flag][1];
        st[node*2][flag][1] %= MOD;
        st[node*2+1][flag][1] += lazy[node][flag][1];
        st[node*2+1][flag][1] %= MOD;
    }
    lazy[node] = {0, 0};
}

void upd2(int node, int l, int r, int l1, int r1, int flag) {
    push(node, l, r, flag);
    if(l1 <= l && r <= r1) {
        lazy[node][flag][1]++;
        st[node][flag][1]++;
        lazy[node][flag][1] %= MOD;
        st[node][flag][1] %= MOD;
        return ;
    }
    if(l1 > r || r1 < l) return;
    int mid = (l+r) >> 1;
    upd2(node*2, l, mid, l1, r1, flag);
    upd2(node*2+1, mid+1, r, l1, r1, flag);
    st[node][flag] = comb(st[node*2][flag], st[node*2+1][flag]);
}

void upd1(int node, int l, int r, int l1, int r1, int flag) {
    push(node, l, r, flag);
    if(l1 <= l && r <= r1) {
        lazy[node][flag] = {1, 1};
        st[node][flag][0]++;
        st[node][flag][1] = 1;
        return ;
    }
    if(l1 > r || r1 < l) return;
    int mid = (l+r) >> 1;
    upd1(node*2, l, mid, l1, r1, flag);
    upd1(node*2+1, mid+1, r, l1, r1, flag);
    st[node][flag] = comb(st[node*2][flag], st[node*2+1][flag]);
}

void upd(int node, int l, int r, int k, array<int, 2> x, int flag) {
    push(node, l, r, flag);
    if(l == r && l == k) {
        if(x[0] > st[node][flag][0]) {
            st[node][flag][0] = x[0];
            st[node][flag][1] = x[1];
        }
        else if(x[0] == st[node][flag][0]) {
            st[node][flag][1] = (st[node][flag][1] + x[1]) % MOD;
        }
        return ;
    }
    if(l > k || r < k) return;
    int mid = (l+r)/2;
    upd(node*2, l, mid, k, x, flag);
    upd(node*2+1, mid+1, r, k, x, flag);
    st[node][flag] = comb(st[node*2][flag], st[node*2+1][flag]);
}

array<int, 2> qry(int node, int l, int r, int l1, int r1, int flag) {
    push(node, l, r, flag);
    if(l1 <= l && r <= r1) {
        return st[node][flag];
    }
    if(l1 > r || r1 < l) return {0, 0};
    int mid = (l+r) >> 1;
    return comb(qry(node*2, l, mid, l1, r1, flag),
                qry(node*2+1, mid+1, r, l1, r1, flag));
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        values.push_back(v[i]);
    }
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    int mn_now = INF, mx_now = 0;
    int mx = 0, cnt = 0;
    stack<int> s1, s2;
    for(auto x : v) {
        x = val(x);
        s1.push(x);
        s2.push(x);
        array<int, 2> now = qry(1, 0, values.size()+1, 0, x-1, 0);
        array<int, 2> now1 = qry(1, 0, values.size()+1, x+1, values.size()+1, 1);
        now[0]++; now1[0]++;
        if(now[1] == 0) now[1] = 1;
        if(now1[1] == 0) now1[1] = 1;
        if(now[0] == mx) {
            cnt = (cnt + now[1]) % MOD;
        }
        else if(now[0] > mx) {
            mx = now[0];
            cnt = now[1];
        }
        if(now1[0] == mx) {
            cnt = (cnt + now1[1]) % MOD;
        }
        else if(now1[0] > mx) {
            mx = now1[0];
            cnt = now1[1];
        }
        if(x < mn_now) {
            while(!s1.empty()) s1.pop();
            upd1(1, 0, values.size()+1, x+1, values.size()+1, 0);
        }
        else if(x == mn_now) {
            upd2(1, 0, values.size()+1, x+1, values.size()+1, 0);
            s1.pop();
            while(!s1.empty()) {
                int y = s1.top();
                s1.pop();
                upd1(1, 0, values.size()+1, y, y, 0);
            }
        }
        if(x > mx_now) {
            while(!s2.empty()) s2.pop();
            upd1(1, 0, values.size()+1, 0, x-1, 1);
        }
        else if(x == mx_now) {
            upd2(1, 0, values.size()+1, 0, x-1, 1);
            s2.pop();
            while(!s2.empty()) {
                int y = s2.top();
                s2.pop();
                upd1(1, 0, values.size()+1, y, y, 1);
            }
        }
        mn_now = min(mn_now, x);
        mx_now = max(mx_now, x);
        upd(1, 0, values.size()+1, x, now, 0);
        upd(1, 0, values.size()+1, x, now1, 1);
    }
    cout << mx << ' ' << cnt;
    return 0;
}

• Subtask 1: 7 / 140