Submission #1276504

#TimeUsernameProblemLanguageResultExecution timeMemory
1276504mehrzadObstacles for a Llama (IOI25_obstacles)C++17
Compilation error
0 ms0 KiB
include <bits/stdc++.h> using namespace std; /*** segment tree for range maximum ***/ struct SegTree { int n; vector<int> seg; SegTree() {} SegTree(const vector<int> &a) { build(a); } void build(const vector<int> &a) { int sz = (int)a.size(); n = 1; while (n < sz) n <<= 1; seg.assign(2 * n, INT_MIN); for (int i = 0; i < sz; ++i) seg[n + i] = a[i]; for (int i = n - 1; i > 0; --i) seg[i] = max(seg[i << 1], seg[i << 1 | 1]); } // inclusive query [l, r] int query(int l, int r) const { l += n; r += n; int res = INT_MIN; while (l <= r) { if (l & 1) res = max(res, seg[l++]); if (!(r & 1)) res = max(res, seg[r--]); l >>= 1; r >>= 1; } return res; } }; /*** DSU ***/ struct DSU { vector<int> p, r; DSU() {} DSU(int n) { init(n); } void init(int n) { p.resize(n); r.assign(n, 0); iota(p.begin(), p.end(), 0); } int find(int x) { if (p[x] == x) return x; return p[x] = find(p[x]); } void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (r[a] < r[b]) swap(a, b); p[b] = a; if (r[a] == r[b]) ++r[a]; } }; /*** global data for the queries ***/ static vector<int> colToSeed; // -1 for non‑seed, otherwise seed index static DSU dsu; static vector<int> seedPos; // column index of each seed (ordered by column) static vector<int> maxDepthSeed; // maxDepth for each seed (by seed index) /*** helpers ***/ static vector<int> prefMin; // size N static vector<int> prefMax; // size N static SegTree segH; // range maximum over H /* binary search: largest i with prefMin[i] > h (seed guarantees existence) */ static int computeMaxDepth(int h) { int lo = 0, hi = (int)prefMin.size(); // hi == N means not found while (lo < hi) { int mid = lo + (hi - lo) / 2; if (prefMin[mid] > h) lo = mid + 1; else hi = mid; } // first index where prefMin <= h is 'lo' return lo - 1; // may become N-1 if never <= h } /*** required functions ***/ void initialize(vector<int> T, vector<int> H) { int N = (int)T.size(); int M = (int)H.size(); /* prefix minima and maxima of temperatures */ prefMin.resize(N); prefMax.resize(N); prefMin[0] = T[0]; prefMax[0] = T[0]; for (int i = 1; i < N; ++i) { prefMin[i] = min(prefMin[i - 1], T[i]); prefMax[i] = max(prefMax[i - 1], T[i]); } /* segment tree on H for interval maximum queries */ segH.build(H); /* seeds */ seedPos.clear(); colToSeed.assign(M, -1); for (int j = 0; j < M; ++j) { if (H[j] < T[0]) { colToSeed[j] = (int)seedPos.size(); seedPos.push_back(j); } } int K = (int)seedPos.size(); dsu.init(K); maxDepthSeed.assign(K, -1); /* maxDepth for each seed */ for (int idx = 0; idx < K; ++idx) { int col = seedPos[idx]; int h = H[col]; maxDepthSeed[idx] = computeMaxDepth(h); } /* order seeds by decreasing maxDepth */ vector<int> order(K); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int a, int b) { return maxDepthSeed[a] > maxDepthSeed[b]; }); /* active set of seed columns (ordered by column) */ set<int> active; // stores column numbers of already inserted seeds for (int idx : order) { int col = seedPos[idx]; int d = maxDepthSeed[idx]; // depth up to which this seed works auto it = active.insert(col).first; // left neighbour if (it != active.begin()) { auto itL = prev(it); int colL = *itL; int idxL = colToSeed[colL]; int intervalMax = segH.query(min(colL, col), max(colL, col)); if (prefMax[d] > intervalMax) dsu.unite(idx, idxL); } // right neighbour auto itR = next(it); if (itR != active.end()) { int colR = *itR; int idxR = colToSeed[colR]; int intervalMax = segH.query(min(col, colR), max(col, colR)); if (prefMax[d] > intervalMax) dsu.unite(idx, idxR); } } } /* L and R are always 0 and M-1, they are ignored */ bool can_reach(int L, int R, int S, int D) { if (S == D) return true; int idS = colToSeed[S]; int idD = colToSeed[D]; if (idS == -1 || idD == -1) return false; // should not happen return dsu.find(idS) == dsu.find(idD); }

Compilation message (stderr)

obstacles.cpp:1:1: error: 'include' does not name a type
    1 | include <bits/stdc++.h>
      | ^~~~~~~
obstacles.cpp:7:5: error: 'vector' does not name a type
    7 |     vector<int> seg;
      |     ^~~~~~
obstacles.cpp:9:19: error: 'vector' does not name a type
    9 |     SegTree(const vector<int> &a) { build(a); }
      |                   ^~~~~~
obstacles.cpp:9:25: error: expected ',' or '...' before '<' token
    9 |     SegTree(const vector<int> &a) { build(a); }
      |                         ^
obstacles.cpp:10:22: error: 'vector' does not name a type
   10 |     void build(const vector<int> &a) {
      |                      ^~~~~~
obstacles.cpp:10:28: error: expected ',' or '...' before '<' token
   10 |     void build(const vector<int> &a) {
      |                            ^
obstacles.cpp: In constructor 'SegTree::SegTree(int)':
obstacles.cpp:9:43: error: 'a' was not declared in this scope
    9 |     SegTree(const vector<int> &a) { build(a); }
      |                                           ^
obstacles.cpp: In member function 'void SegTree::build(int)':
obstacles.cpp:11:23: error: 'a' was not declared in this scope
   11 |         int sz = (int)a.size();
      |                       ^
obstacles.cpp:14:9: error: 'seg' was not declared in this scope
   14 |         seg.assign(2 * n, INT_MIN);
      |         ^~~
obstacles.cpp:14:27: error: 'INT_MIN' was not declared in this scope
   14 |         seg.assign(2 * n, INT_MIN);
      |                           ^~~~~~~
obstacles.cpp:1:1: note: 'INT_MIN' is defined in header '<climits>'; did you forget to '#include <climits>'?
  +++ |+#include <climits>
    1 | include <bits/stdc++.h>
obstacles.cpp:16:50: error: 'max' was not declared in this scope
   16 |         for (int i = n - 1; i > 0; --i) seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
      |                                                  ^~~
obstacles.cpp: In member function 'int SegTree::query(int, int) const':
obstacles.cpp:21:19: error: 'INT_MIN' was not declared in this scope
   21 |         int res = INT_MIN;
      |                   ^~~~~~~
obstacles.cpp:21:19: note: 'INT_MIN' is defined in header '<climits>'; did you forget to '#include <climits>'?
obstacles.cpp:23:39: error: 'seg' was not declared in this scope
   23 |             if (l & 1) res = max(res, seg[l++]);
      |                                       ^~~
obstacles.cpp:23:30: error: 'max' was not declared in this scope
   23 |             if (l & 1) res = max(res, seg[l++]);
      |                              ^~~
obstacles.cpp:24:42: error: 'seg' was not declared in this scope
   24 |             if (!(r & 1)) res = max(res, seg[r--]);
      |                                          ^~~
obstacles.cpp:24:33: error: 'max' was not declared in this scope
   24 |             if (!(r & 1)) res = max(res, seg[r--]);
      |                                 ^~~
obstacles.cpp: At global scope:
obstacles.cpp:33:5: error: 'vector' does not name a type
   33 |     vector<int> p, r;
      |     ^~~~~~
obstacles.cpp: In member function 'void DSU::init(int)':
obstacles.cpp:37:9: error: 'p' was not declared in this scope
   37 |         p.resize(n);
      |         ^
obstacles.cpp:38:9: error: 'r' was not declared in this scope
   38 |         r.assign(n, 0);
      |         ^
obstacles.cpp:39:9: error: 'iota' was not declared in this scope
   39 |         iota(p.begin(), p.end(), 0);
      |         ^~~~
obstacles.cpp: In member function 'int DSU::find(int)':
obstacles.cpp:42:13: error: 'p' was not declared in this scope
   42 |         if (p[x] == x) return x;
      |             ^
obstacles.cpp:43:16: error: 'p' was not declared in this scope
   43 |         return p[x] = find(p[x]);
      |                ^
obstacles.cpp: In member function 'void DSU::unite(int, int)':
obstacles.cpp:48:13: error: 'r' was not declared in this scope
   48 |         if (r[a] < r[b]) swap(a, b);
      |             ^
obstacles.cpp:48:26: error: 'swap' was not declared in this scope
   48 |         if (r[a] < r[b]) swap(a, b);
      |                          ^~~~
obstacles.cpp:49:9: error: 'p' was not declared in this scope
   49 |         p[b] = a;
      |         ^
obstacles.cpp:50:13: error: 'r' was not declared in this scope
   50 |         if (r[a] == r[b]) ++r[a];
      |             ^
obstacles.cpp: At global scope:
obstacles.cpp:55:8: error: 'vector' does not name a type
   55 | static vector<int> colToSeed;   // -1 for non‑seed, otherwise seed index
      |        ^~~~~~
obstacles.cpp:57:8: error: 'vector' does not name a type
   57 | static vector<int> seedPos;     // column index of each seed (ordered by column)
      |        ^~~~~~
obstacles.cpp:58:8: error: 'vector' does not name a type
   58 | static vector<int> maxDepthSeed; // maxDepth for each seed (by seed index)
      |        ^~~~~~
obstacles.cpp:61:8: error: 'vector' does not name a type
   61 | static vector<int> prefMin;   // size N
      |        ^~~~~~
obstacles.cpp:62:8: error: 'vector' does not name a type
   62 | static vector<int> prefMax;   // size N
      |        ^~~~~~
obstacles.cpp: In function 'int computeMaxDepth(int)':
obstacles.cpp:67:27: error: 'prefMin' was not declared in this scope
   67 |     int lo = 0, hi = (int)prefMin.size(); // hi == N means not found
      |                           ^~~~~~~
obstacles.cpp: At global scope:
obstacles.cpp:78:6: error: variable or field 'initialize' declared void
   78 | void initialize(vector<int> T, vector<int> H) {
      |      ^~~~~~~~~~
obstacles.cpp:78:17: error: 'vector' was not declared in this scope
   78 | void initialize(vector<int> T, vector<int> H) {
      |                 ^~~~~~
obstacles.cpp:78:24: error: expected primary-expression before 'int'
   78 | void initialize(vector<int> T, vector<int> H) {
      |                        ^~~
obstacles.cpp:78:32: error: 'vector' was not declared in this scope
   78 | void initialize(vector<int> T, vector<int> H) {
      |                                ^~~~~~
obstacles.cpp:78:39: error: expected primary-expression before 'int'
   78 | void initialize(vector<int> T, vector<int> H) {
      |                                       ^~~
obstacles.cpp: In function 'bool can_reach(int, int, int, int)':
obstacles.cpp:154:15: error: 'colToSeed' was not declared in this scope
  154 |     int idS = colToSeed[S];
      |               ^~~~~~~~~