結果
問題 | No.2956 Substitute with Average |
ユーザー |
![]() |
提出日時 | 2024-11-09 00:31:57 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 677 ms / 3,000 ms |
コード長 | 3,777 bytes |
コンパイル時間 | 3,111 ms |
コンパイル使用メモリ | 247,868 KB |
実行使用メモリ | 172,416 KB |
最終ジャッジ日時 | 2024-11-09 00:32:12 |
合計ジャッジ時間 | 13,755 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using ld = long double;using ull = unsigned long long;template <class T>using max_heap = priority_queue<T>;template <class T>using min_heap = priority_queue<T, vector<T>, greater<T>>;#define rep(i, l, r) for (ll i = (l); i < (r); i++)#define rrep(i, r, l) for (ll i = (r); i-- > (l);)#define all(x) begin(x), end(x)template <class T>bool chmin(T& lhs, T rhs) {return lhs > rhs ? (lhs = rhs, true) : false;}template <class T>bool chmax(T& lhs, T rhs) {return lhs < rhs ? (lhs = rhs, true) : false;}struct IOIO {IOIO() {cin.tie(0)->sync_with_stdio(0);}} ioio;template <class S, class T>ostream& operator<<(ostream& os, const pair<S, T>& p) {os << '(' << p.first << ", " << p.second << ')';return os;}template <class T>ostream& operator<<(ostream& os, const vector<T>& vs) {os << '{';rep(i, 0, (int)vs.size()) os << vs[i] << (i + 1 == (int)vs.size() ? "" : ", ");os << '}';return os;}template <class T>ostream& operator<<(ostream& os, const set<T>& vs) {os << '{';for (auto it = vs.begin(); it != vs.end(); it++) {if (it != vs.begin()) {os << ", ";}os << *it;}os << '}';return os;}template <class T, class U>ostream& operator<<(ostream& os, const map<T, U>& vs) {os << '{';for (auto it = vs.begin(); it != vs.end(); it++) {if (it != vs.begin()) {os << ", ";}os << *it;}os << '}';return os;}#ifdef DEBUGvoid dump_func() {cerr << endl;}template <class Head, class... Tail>void dump_func(Head&& head, Tail&&... tail) {cerr << head;if (sizeof...(Tail) > 0) {cerr << ", ";}dump_func(std::move(tail)...);}#define dump(...) cerr << "[" + string(#__VA_ARGS__) + "] ", dump_func(__VA_ARGS__)#else#define dump(...) static_cast<int>(0)#endifconstexpr int N = 2 * 100000 * 32;constexpr int OFFSET = 100000 * 32;int MP[31][N];int SUM[31];void solve() {int n;cin >> n;vector<int> a(n);rep(i, 0, n) cin >> a[i];ll ans = (ll)n * (n + 1) / 2 - n;auto DnC = [&](auto&& self, int l, int r) -> void {if (l + 1 == r) return;int m = (l + r) / 2;self(self, l, m);self(self, m, r);rep(x, 1, 31) {int sum = 0;rep(i, m, r) {sum += a[i];MP[a[i]][(i - m + 1) * x - sum + OFFSET]++;}sum = 0;rrep(i, m, l) {sum += a[i];if (a[i] == x) ans += MP[a[i]][sum - a[i] * (m - i) + OFFSET];}sum = 0;rep(i, m, r) {sum += a[i];MP[a[i]][(i - m + 1) * x - sum + OFFSET]--;}}};auto DnC2 = [&](auto&& self, int l, int r) -> void {if (l + 1 == r) return;int m = (l + r) / 2;self(self, l, m);self(self, m, r);rep(x, 1, 31) {int sum = 0;rep(i, m, r) {sum += a[i];MP[x][(i - m + 1) * x - sum + OFFSET]++;}}{int sum = 0;rrep(i, m, l) {sum += a[i];ans -= MP[a[i]][sum - a[i] * (m - i) + OFFSET];}}rep(x, 1, 31) {int sum = 0;rep(i, m, r) {sum += a[i];MP[x][(i - m + 1) * x - sum + OFFSET]--;}}};DnC(DnC, 0, n);DnC2(DnC2, 0, n);reverse(all(a));DnC2(DnC2, 0, n);cout << ans + 1 << '\n';}int main() {int t = 1;while (t--) solve();}