Submission #1341377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1341377		LucasLe	Exhibition 3 (JOI25_exhibition3)	C++20	Compilation error	0 ms	0 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Lazy Segment Tree to support Range Max Query and Range Assignment
struct SegTree {
    int n;
    vector<int> tree;
    vector<int> lazy;

    SegTree(int n) {
        this->n = n;
        tree.assign(4 * n + 1, -1);
        lazy.assign(4 * n + 1, -2); // -2 represents "no pending update"
    }

    void push(int node) {
        if (lazy[node] != -2) {
            tree[2 * node] = lazy[node];
            lazy[2 * node] = lazy[node];
            tree[2 * node + 1] = lazy[node];
            lazy[2 * node + 1] = lazy[node];
            lazy[node] = -2;
        }
    }

    void update(int node, int l, int r, int ql, int qr, int val) {
        if (ql <= l && r <= qr) {
            tree[node] = val;
            lazy[node] = val;
            return;
        }
        push(node);
        int mid = l + (r - l) / 2;
        if (ql <= mid) update(2 * node, l, mid, ql, qr, val);
        if (qr > mid)  update(2 * node + 1, mid + 1, r, ql, qr, val);
        tree[node] = max(tree[2 * node], tree[2 * node + 1]);
    }

    int query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return tree[node];
        }
        push(node);
        int mid = l + (r - l) / 2;
        int res = -1;
        if (ql <= mid) res = max(res, query(2 * node, l, mid, ql, qr));
        if (qr > mid)  res = max(res, query(2 * node + 1, mid + 1, r, ql, qr));
        return res;
    }
};

int main() {
    // Optimize standard I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    SegTree st(N);
    vector<int> L_act(N + 1, -1);
    vector<int> R_act(N + 1, -1);
    
    int e = N; // e tracks the largest available unassigned (empty) beauty value

    for (int j = 0; j < M; ++j) {
        int L, R;
        cin >> L >> R;

        // Query the max active intersecting beauty
        int v = st.query(1, 1, N, L, R);
        int ans = -1;

        if (e > v) {
            // Assign a completely new beauty 'e'
            ans = e;
            e--;
            L_act[ans] = L;
            R_act[ans] = R;
            st.update(1, 1, N, L, R, ans);
        } else {
            // Intersect with an already assigned beauty 'v'
            ans = v;
            int new_L = max(L_act[ans], L);
            int new_R = min(R_act[ans], R);

            // Remove the overhangs by resetting them to -1
            if (L_act[ans] < new_L) {
                st.update(1, 1, N, L_act[ans], new_L - 1, -1);
            }
            if (new_R < R_act[ans]) {
                st.update(1, 1, N, new_R + 1, R_act[ans], -1);
            }

            L_act[ans] = new_L;
            R_act[ans] = new_R;
        }

        cout << ans << "\n";

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:107:29: error: expected '}' at end of input
  107 |         cout << ans << "\n";
      |                             ^
Main.cpp:74:33: note: to match this '{'
   74 |     for (int j = 0; j < M; ++j) {
      |                                 ^
Main.cpp:107:29: error: expected '}' at end of input
  107 |         cout << ans << "\n";
      |                             ^
Main.cpp:55:12: note: to match this '{'
   55 | int main() {
      |            ^