Submission #1016424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016424		asdfgrace	Stranded Far From Home (BOI22_island)	C++17	20 / 100	205 ms	37972 KiB

island

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

#define dbg(x) //x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<long long> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  bool inc = false;
  for (int i = 0; i < n - 1; i++) {
    if (s[i + 1] > s[i]) {
      inc = true;
    }
  }
  bool dif1 = true;
  vector<vector<int>> edges(n);
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    if (abs(x - y) > 1) dif1 = false;
    edges[x].push_back(y);
    edges[y].push_back(x);
  }
  if (n <= 2000 && m <= 2000) {
    for (int i = 0; i < n; i++) {
      vector<bool> vis(n, false);
      vis[i] = true;
      priority_queue<array<long long, 2>> que;
      que.push({-s[i], i});
      bool ok = true;
      long long tot = s[i];
      while (que.size()) {
        long long sz = -que.top()[0], node = que.top()[1];
        que.pop();
        if (sz > tot) {
          ok = false;
          break;
        }
        if (node != i) {
          tot += sz;
        }
        for (auto next : edges[node]) {
          if (!vis[next]) {
            vis[next] = true;
            que.push({-s[next], next});
          }
        }
      }
      cout << (ok ? 1 : 0);
    }
    cout << '\n';
  } else if (m == n - 1 && !inc) {
    vector<bool> ok(n, true);
    vector<long long> sum = s;
    function<void(int, int)> dfs1 = [&] (int node, int par) {
      for (auto next : edges[node]) {
        if (next != par) {
          dfs1(next, node);
          sum[node] += sum[next];
        }
      }
    };
    dfs1(0, 0);
    function<void(int, int)> dfs2 = [&] (int node, int par) {
      if (node != 0) {
        ok[node] = ok[par];
        if (s[par] > sum[node]) {
          ok[node] = false;
        }
      }
      for (auto next : edges[node]) {
        if (next != par) {
          dfs2(next, node);
        }
      }
    };
    dfs2(0, 0);
    for (int i = 0; i < n; i++) {
      cout << (ok[i] ? 1 : 0);
    }
    cout << '\n';
  } else if (dif1) {
    /*
    other way around: look for all pairs of walls
    so that sum between the walls < min val of the 2 walls
    note: may be single elem restricting lb/rb
    so if this elem > sum of pref, nothing before it works
    or if elem > sum of suf, nothing after it works
    after finding these
    for every l wall
    what's max r wall
    within the range of r so that sum(l+1...r-1) < a[l]
    (mxr = lower_bound(a.begin(), a.end(), pref[l] + a[l]))
    (mxr maybe not monotonic - use segtree?)
    (finding max ind)
    (upd segtree and process inds in order of r)
    sum(l+1...r-1) < a[r] --> rightmost in [l+1,mxr] so that mnl[r] <= l
    so max segtree
    when time comes, st[i] = i
    process l in order
    update the segtree
    before processing each l
    update each segtree index
    so that mnl[r] <= l
    */
    vector<long long> ps = s;
    for (int i = 1; i < n; i++) {
      ps[i] += ps[i - 1];
    }
    vector<bool> ok(n, true);
    for (int i = n - 1; i > 0; i--) {
      if (s[i] > ps[i - 1]) {
        for (int j = 0; j < i; j++) {
          ok[j] = false;
        }
        break;
      }
    }
    for (int i = 0; i < n - 1; i++) {
      if (s[i] > ps[n - 1] - ps[i]) {
        for (int j = i + 1; j < n; j++) {
          ok[j] = false;
        }
        break;
      }
    }
    parr(ok);
    vector<int> mxr(n), mnl(n);
    for (int i = 0; i < n; i++) {
      mxr[i] = lower_bound(ps.begin(), ps.end(), ps[i] + s[i]) - ps.begin();
      mnl[i] = upper_bound(ps.begin(), ps.end(), ps[i] - 2 * s[i]) - ps.begin() - 1;
      mxr[i] = min(mxr[i], n - 1);
      mnl[i] = max(mnl[i], 0);
    }
    parr(mnl); parr(mxr);
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&] (int x, int y) {
      return mnl[x] < mnl[y];
    });
    vector<int> st(2 * n, -1);
    function<void(int, int)> upd = [&] (int ind, int val) {
      ind += n; st[ind] = val;
      for (int i = ind / 2; i > 0; i /= 2) {
        st[i] = max(st[i * 2], st[i * 2 + 1]);
      }
    };
    function<int(int, int)> quer = [&] (int l, int r) {
      l += n; r += n;
      int mx = -1;
      while (l <= r) {
        if (l % 2 == 1) mx = max(mx, st[l++]);
        if (r % 2 == 0) mx = max(mx, st[r--]);
        l /= 2; r /= 2;
      }
      return mx;
    };
    int it = 0;
    vector<int> stat(n, 0), enat(n, 0);
    for (int l = 0; l < n; l++) {
      pv(l);
      while (it < n && mnl[ord[it]] <= l) {
        upd(ord[it], ord[it]);
        it++;
      }
      if (mxr[l] >= l + 1) {
        int best = quer(l + 1, mxr[l]);
        pv(best);
        if (best != -1) {
          stat[l + 1]++;
          enat[best]++;
        }
      }
    }
    int cur = 0;
    for (int i = 0; i < n; i++) {
      cur -= enat[i];
      cur += stat[i];
      if (cur > 0) ok[i] = false;
    }
    for (int i = 0; i < n; i++) {
      cout << (ok[i] ? '1' : '0');
    }
    cout << '\n';
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35