oj.uz

Submission #968022

# Submission time Handle Problem Language Result Execution time Memory
968022 2024-04-23T06:58:32 Z Pring Real Mountains (CCO23_day1problem2) C++17
0 / 25
 1 ms 6488 KB 
#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(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);
    return ((t1 - t0) * (A + D + min(B, C) + 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--;
        }
    }
    cout << ans << '\n';
}

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

Compilation message

Main.cpp: In function 'void miku()':
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:127:9: note: in expansion of macro 'debug'
  127 |         debug(t);
      |         ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:129:13: note: in expansion of macro 'debug'
  129 |             debug("KICK", id);
      |             ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:132:13: note: in expansion of macro 'debug'
  132 |             debug("PUSH", id);
      |             ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:136:13: note: in expansion of macro 'debug'
  136 |             debug("POP", id);
      |             ^~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -