Submission #1263320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263320		rtri	Spiral (BOI16_spiral)	C++20	0 / 100	152 ms	448 KiB

spiral

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

vector<vector<int>> grid;

typedef long long int ll;

ll MOD = 1e9 + 7;

ll at_poll(ll x, ll y) {
  y *= -1;

  if (x == 0 && y == 0)
    return 1;

  ll loc = max(abs(x), abs(y));
  ll slen = (2 * loc - 1);
  ll val = slen * slen;

  if (y == loc)
    val += 6 * loc + loc + x;
  else if (x == -loc)
    val += 4 * loc + loc + y;
  else if (y == -loc)
    val += 2 * loc + loc - x;
  else if (x == loc)
    val += loc - y;

  return val;
}

class ST {
  int st_n;
  vector<ll> val;

public:
  ST(int n) : val(2 * n) { st_n = n; }
  void update(int i, int v) {
    i += st_n;
    for (val[i] = (val[i] + v) % MOD; i > 1; i >>= 1)
      val[i >> 1] = (val[i] + val[i ^ 1]) % MOD;
  }
  ll query(int l, int r) {
    ll res = 0;
    for (l += st_n, r += st_n; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        res += val[l++];
      if (r & 1)
        res += val[--r];
      res %= MOD;
    }
    return res;
  }
};

int main() {
  int n, q;
  cin >> n >> q;

  vector<ll> ans(q);
  vector<tuple<int, int, int, int, int>> queries;

  ST pref(2 * n + 1);

  for (int i = 0; i < q; i++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    queries.push_back({y1 - 1, x1, x2, i, -1});
    queries.push_back({y2, x1, x2, i, 1});
  }

  sort(queries.begin(), queries.end());

  int query_idx = 0;
  while (query_idx < queries.size() && get<0>(queries[query_idx]) < -n)
    query_idx++;

  for (int y = -n; y <= n; y++) {
    for (int x = -n; x <= n; x++)
      pref.update(n + x, at_poll(x, y));

    while (query_idx < queries.size() && get<0>(queries[query_idx]) == y) {
      auto [_y, x1, x2, idx, mul] = queries[query_idx];
      ans[idx] += pref.query(n + x1, n + x2 + 1) * mul;
      query_idx++;
    }
  }

  for (int i = 0; i < q; i++)
    cout << ans[i] % MOD << endl;

  return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 31
• Subtask 5: 0 / 25