Submission #1199804

#TimeUsernameProblemLanguageResultExecution timeMemory
1199804Nelt모자이크 (IOI24_mosaic)C++20
100 / 100
950 ms182304 KiB
#include "mosaic.h" #include <bits/stdc++.h> #define ll long long // #define endl "\n" using namespace std; const ll N = 2e5 + 5; ll t[N]; void upd(ll i, ll d) { for (; i < N; i |= (i + 1)) t[i] += d; } ll sum(ll i) { ll ans = 0; for (; i >= 0; i = (i & (i + 1)) - 1) ans += t[i]; return ans; } vector<ll> neg, pos, pneg, ppos; map<ll, ll> mp[N]; map<ll, vector<pair<ll, ll>>> diag; vector<array<ll, 3>> inc; ll n, q; void precomp() { for (ll i = 1; i < n; i++) for (ll j = 1; j < n; j++) { if (i > 2 and j > 2) break; mp[i][j] = !mp[i - 1][j] and !mp[i][j - 1]; diag[j - i].push_back(make_pair(i, j)); } pos.push_back(0); for (auto [x, v] : diag) if (v.size() == 1) { if (mp[v[0].first][v[0].second]) inc.push_back({v[0].first, v[0].second, 1}); } else { assert(v[0].first < v[1].first); if (mp[v[0].first][v[0].second]) { if (x < 0) neg.push_back(-x); else pos.push_back(x); } else if (mp[v[1].first][v[1].second]) { inc.push_back({v[0].first, v[0].second, -1}); if (x < 0) neg.push_back(-x); else pos.push_back(x); } } neg.push_back(0); reverse(neg.begin(), neg.end()); // for (auto [a, b, c] : inc) cout << a << " " << b << " " << c << endl; pneg.push_back(0); ppos.push_back(0); // cout << pos.size() << " " << neg.size() << endl; // for (ll i : pos) cout << i << " "; // cout << endl; // for (ll i : neg) cout << i << " "; // cout << endl; for (ll i = 1; i < neg.size(); i++) pneg.push_back(pneg.back() + neg[i]); for (ll i = 1; i < pos.size(); i++) ppos.push_back(ppos.back() + pos[i]); sort(inc.begin(), inc.end()); } ll sum(ll l, ll r, vector<ll> &pref) { r = min(r, (ll)pref.size() - 1); l = max(0ll, l - 1); return l >= r ? 0 : pref[r] - pref[l]; } ll calc(ll i, ll j, vector<ll> &v, vector<ll> &pref) { if (j < 0 or i < 0) return 0; ll l = upper_bound(v.begin() + 1, v.end(), j - i) - v.begin(), r = upper_bound(v.begin() + 1, v.end(), j) - v.begin(); return (l - 1) * i + j * (r - l) - sum(l, r - 1, pref); // ll ans = (l - 1) * i + (r - l) * j; // ans -= sum(l, r - 1, pref); // return ans; } ll f(ll i, ll j) { return calc(i, j, pos, ppos) + calc(j, i, neg, pneg); } // i <= j - x -> x <= j - i // i <= j - x -> i + x <= j -> x <= j - i // i > j - x, +j * sz pref[] // i <= j - x, then i > j - x (j - x might become less than 0, so need to keep track) // max(i, j - x) -> x > 0 // max(i + x, j) -> x <= 0 (max(i, j - x), ij swapped, negative turned to positive) vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) { n = X.size(), q = T.size(); for (ll i = 0; i < n; i++) mp[0][i] = X[i], mp[i][0] = Y[i]; for (ll i = 0; i < n; i++) { if (X[i]) inc.push_back({0, i, 1}); if (Y[i] and i) inc.push_back({i, 0, 1}); } precomp(); array<ll, 3> qs[q << 2]; vector<ll> ans(q, 0); // cout << "all good\n"; for (ll i = 0; i < q; i++) { qs[i * 4] = {T[i] - 1, L[i] - 1, i * 4}; qs[i * 4 + 1] = {B[i], R[i], i * 4 + 1}; qs[i * 4 + 2] = {T[i] - 1, R[i], i * 4 + 2}; qs[i * 4 + 3] = {B[i], L[i] - 1, i * 4 + 3}; } sort(qs, qs + q * 4); ll ptr = 0; for (auto [x, y, ind] : qs) { ll id = (ind >> 2), tp = (ind & 3) < 2 ? 1 : -1; while (ptr < inc.size() and inc[ptr][0] <= x) upd(inc[ptr][1], inc[ptr][2]), ptr++; ans[id] += tp * (sum(y) + f(x, y)); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...