Submission #968037

#	Time	Username	Problem	Language	Result	Execution time	Memory
968037		Pring	Real Mountains (CCO23_day1problem2)	C++17	10 / 25	825 ms	84896 KiB

Main

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

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef array<int, 3> p3i;

const int MXN = 1000005, mod = 1000003, INF = 2e9;
int n, a[MXN];
int tg[MXN], cnt;
vector<p3i> op;

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

pii operator+(pii a, pii b) {
    return mp(min(a.fs, b.fs), max(a.sc, b.sc));
}

struct SMG1 {
    pii val[MXN * 2];
    void init(int _n) {
        fill(val, val + 2 * n, mp(INF, -INF));
    }
    void modify(int p, pii v) {
        val[p += n] = v;
        for (p >>= 1; p; p >>= 1) val[p] = val[p << 1] + val[p << 1 | 1];
    }
    pii query(int l, int r) {
        pii ans = mp(INF, -INF);
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ans = ans + val[l++];
            if (r & 1) ans = ans + val[--r];
        }
        return ans;
    }
} S;

struct SMG2 {
    int val[MXN * 2];
    void init(int n, int *a) {
        copy(a, a + n, val + n);
        for (int i = n - 1; i; i--) val[i] = min(val[i << 1], val[i << 1 | 1]);
    }
    void modify(int p, int v) {
        val[p += n] = v;
        for (p >>= 1; p; p >>= 1) val[p] = min(val[p << 1], val[p << 1 | 1]);
    }
    int query(int l, int r) {
        int ans = INF;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ans = min(ans, val[l++]);
            if (r & 1) ans = min(ans, val[--r]);
        }
        return ans;
    }
} smg;

void GET_TG() {
    int l = 0, r = n - 1;
    int now = 0, big = *max_element(a, a + n);
    while (a[l] < big) {
        now = max(now, a[l]);
        tg[l] = now;
        l++;
    }
    now = 0;
    while (a[r] < big) {
        now = max(now, a[r]);
        tg[r] = now;
        r--;
    }
    FOR(i, l, r + 1) tg[i] = big;
}

int calc(int t0, int t1) {
    if (cnt == 0) return 0;
    if (t0 == t1) return 0;
    debug("CALC", t0, t1, cnt);
    if (cnt == 1) {
        int x = S.query(0, n).fs;
        int A = smg.query(0, x), B = smg.query(x + 1, n);
        return ((t1 - t0) * (A + B) + tri(t0, t1)) % mod;
    }
    auto [l, r] = S.query(0, n);
    int A = smg.query(0, l), B = smg.query(l + 1, n);
    int C = smg.query(0, r), D = smg.query(r + 1, n);
    debug(A, B, C, D);
    return ((t1 - t0) * (A + D + min(B, C) + 2 * cnt - 3) % mod + (3 * cnt - 3) * tri(t0, t1) % mod) % mod;
}

void miku() {
    cin >> n;
    FOR(i, 0, n) cin >> a[i];
    GET_TG();
    // FOR(i, 0, n) cout << a[i] << ' ';
    // cout << endl;
    // FOR(i, 0, n) cout << tg[i] << ' ';
    // cout << endl;
    S.init(n);
    smg.init(n, a);
    FOR(i, 0, n) {
        op.push_back(p3i{a[i], 1, i});
        op.push_back(p3i{a[i], 2, i});
        op.push_back(p3i{tg[i], 3, i});
    }
    sort(op.begin(), op.end());
    int time = 0;
    ll ans = 0;
    for (auto [t, tp, id] : op) {
        ans = (ans + calc(time, t)) % mod;
        time = t;
        debug(t);
        if (tp == 1) {
            debug("KICK", id);
            smg.modify(id, INF);
        } else if (tp == 2) {
            debug("PUSH", id);
            S.modify(id, mp(id, id));
            cnt++;
        } else {
            debug("POP", id);
            S.modify(id, mp(INF, -INF));
            cnt--;
        }
        debug(ans);
    }
    cout << ans << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int calc(int, int)':
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:94:5: note: in expansion of macro 'debug'
   94 |     debug("CALC", t0, t1, cnt);
      |     ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:103:5: note: in expansion of macro 'debug'
  103 |     debug(A, B, C, D);
      |     ^~~~~
Main.cpp: In function 'void miku()':
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:128:9: note: in expansion of macro 'debug'
  128 |         debug(t);
      |         ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:130:13: note: in expansion of macro 'debug'
  130 |             debug("KICK", id);
      |             ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:133:13: note: in expansion of macro 'debug'
  133 |             debug("PUSH", id);
      |             ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:137:13: note: in expansion of macro 'debug'
  137 |             debug("POP", id);
      |             ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:141:9: note: in expansion of macro 'debug'
  141 |         debug(ans);
      |         ^~~~~

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