Submission #968063

#	Time	Username	Problem	Language	Result	Execution time	Memory
968063		becaido	Real Mountains (CCO23_day1problem2)	C++17	25 / 25	1995 ms	76248 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int INF = 2e9;
const int MOD = 1e6 + 3;
const int SIZE = 1e6 + 5;

int n, mx;
ll ans;
int a[SIZE];
pair<int, int> val[SIZE];

ll sum(int l, int r) {
    return 1ll * (r - l + 1) * (l + r) / 2 % MOD;
}

int mn[SIZE << 2];
void build(int pos, int l, int r) {
    if (l == r) {
        mn[pos] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(lpos, l, mid);
    build(rpos, mid + 1, r);
    mn[pos] = min(mn[lpos], mn[rpos]);
}
void upd(int pos, int l, int r, int p) {
    if (l == r) {
        mn[pos] = INF;
        return;
    }
    int mid = (l + r) / 2;
    if (p <= mid) upd(lpos, l, mid, p);
    else upd(rpos, mid + 1, r, p);
    mn[pos] = min(mn[lpos], mn[rpos]);
}
int que(int pos, int l, int r, int L, int R) {
    if (l == L && r == R) return mn[pos];
    int mid = (L + R) / 2;
    if (r <= mid) return que(lpos, l, r, L, mid);
    if (l > mid) return que(rpos, l, r, mid + 1, R);
    return min(que(lpos, l, mid, L, mid), que(rpos, mid + 1, r, mid + 1, R));
}

set<int> s;

void solve() {
    cin >> n;
    FOR (i, 1, n) cin >> a[i], val[i] = {a[i], i};
    sort(val + 1, val + n + 1);
    build(1, 1, n);

    FOR (vi, 1, n - 1) {
        s.insert(val[vi].S);
        upd(1, 1, n, val[vi].S);
        if (val[vi].F == val[vi + 1].F) continue;

        int x = val[vi].F, y = val[vi + 1].F - 1, len = y - x + 1;
        int lmn = 0, rmn = 0, lv = 0, rv = 0;

        while (s.size()) {
            int i = *s.begin(), mn = INF;
            if (i > 1) mn = que(1, 1, i - 1, 1, n);
            if (mn == INF) {
                s.erase(s.begin());
                continue;
            }
            lmn = mn;
            break;
        }
        while (s.size()) {
            int i = *prev(s.end()), mn = INF;
            if (i < n) mn = que(1, i + 1, n, 1, n);
            if (mn == INF) {
                s.erase(prev(s.end()));
                continue;
            }
            rmn = mn;
            break;
        }
        if (s.size() == 0) continue;

        lv = que(1, *s.begin() + 1, n, 1, n);
        rv = que(1, 1, *prev(s.end()) - 1, 1, n);

        if (s.size() == 1) ans += 1ll * len * (lmn + rmn) + sum(x, y);
        else ans += 1ll * len * ((ll) lmn + min(lv, rv) + rmn + 1) % MOD + 3 * sum(x, y) + 1ll * (s.size() - 2) * (3 * sum(x, y) + 2 * len) % MOD;
        ans %= MOD;
    }
    cout << ans << '\n';
}

int main() {
    Waimai;
    solve();
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 3 / 3
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 4 / 4