結果
| 問題 | No.404 部分門松列 |
| ユーザー |
 Aoxiang Cui
|
| 提出日時 | 2021-08-29 20:00:24 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 402 ms / 2,000 ms |
| コード長 | 5,145 bytes |
| コンパイル時間 | 3,226 ms |
| コンパイル使用メモリ | 134,640 KB |
| 実行使用メモリ | 23,676 KB |
| 最終ジャッジ日時 | 2024-11-22 08:00:15 |
| 合計ジャッジ時間 | 10,873 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 31 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:168:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
168 | for (auto& [k, v] : cnt) if (v) B.push_back({k, v});
| ^
ソースコード
// #define LOCAL#define _USE_MATH_DEFINES#include <array>#include <cassert>#include <cstdio>#include <cstring>#include <iostream>#include <iomanip>#include <string>#include <sstream>#include <vector>#include <queue>#include <stack>#include <list>#include <set>#include <map>#include <unordered_set>#include <unordered_map>#include <algorithm>#include <complex>#include <cmath>#include <numeric>#include <bitset>#include <functional>#include <random>#include <ctime>using namespace std;template <typename A, typename B>ostream& operator <<(ostream& out, const pair<A, B>& a) {out << "(" << a.first << "," << a.second << ")";return out;}template <typename T, size_t N>ostream& operator <<(ostream& out, const array<T, N>& a) {out << "["; bool first = true;for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";return out;}template <typename T>ostream& operator <<(ostream& out, const vector<T>& a) {out << "["; bool first = true;for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";return out;}template <typename T, class Cmp>ostream& operator <<(ostream& out, const set<T, Cmp>& a) {out << "{"; bool first = true;for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";return out;}template <typename U, typename T, class Cmp>ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {out << "{"; bool first = true;for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";return out;}#ifdef LOCAL#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)#else#define trace(...) 42#endiftemplate <typename Arg1>void __f(const char* name, Arg1&& arg1){cerr << name << ": " << arg1 << endl;}template <typename Arg1, typename... Args>void __f(const char* names, Arg1&& arg1, Args&&... args){const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << ": " << arg1 << " |";__f(comma + 1, args...);}template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); }template <class T, class... D> auto vect(const T& v, int n, D... m) {return vector<decltype(vect(v, m...))>(n, vect(v, m...));}typedef long long int64;typedef pair<int64, int64> ii;#define SZ(x) (int)((x).size())template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;const int MOD = 1e9 + 7;// const int MOD = 998244353;mt19937 mrand(random_device{}());int rnd(int x) { return mrand() % x; }// mt19937_64 mrand(random_device{}());// int64 rnd(int64 x) { return mrand() % x; }template <class T> void out(const vector<T>& a) { for (int i = 0; i < SZ(a); ++i) cout << a[i] << " \n"[i + 1 == SZ(a)]; }template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }template <class T> void dedup(vector<T>& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); }void add(int& x, int y) { x += y; if (x >= MOD) x -= MOD; }struct fast_ios {fast_ios() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(10);};} fast_ios_;template<typename T, size_t N>struct fenwick {T c[N];fenwick() {fill(c + 1, c + N, 0);}void add(int x, T y) {for (; x < N; x += x & -x) {c[x] += y;}}T query(int x) {T ret = 0;for (; x; x -= x & -x) {ret += c[x];}return ret;}};int main() {int n;cin >> n;vector<int> a(n), A;for (auto& x : a) {cin >> x;A.push_back(x);}dedup(A);vector<int> b(n);for (int i = 0; i < n; ++i) b[i] = lower_bound(A.begin(), A.end(), a[i]) - A.begin() + 1;const int N = 2e5 + 10;fenwick<int64, N> F, G, H;int64 sum = 0;for (int i = 1; i < n; ++i) G.add(b[i], 1);map<int, int64> cnt;for (int i = 0; i < n; ++i) {int64 ll = F.query(b[i] - 1), ll2 = F.query(b[i]);int64 rr = G.query(b[i] - 1), rr2 = G.query(b[i]);int64 ss = H.query(b[i] - 1), ss2 = H.query(b[i]);int64 cur = ll * rr +(i - ll2) * (n - 1 - i - rr2) -ss - (sum - ss2);trace(i, a[i], b[i], ll, rr, ll2, rr2, ss, ss2, sum, cur);cnt[a[i]] += cur;if (i + 1 < n) {int64 ff = F.query(b[i + 1]) - F.query(b[i + 1] - 1);int64 gg = G.query(b[i]) - G.query(b[i] - 1);int64 dd = gg - ff;if (b[i] == b[i + 1]) dd--;sum += dd;H.add(b[i], gg);H.add(b[i + 1], -ff);if (b[i] == b[i + 1]) H.add(b[i], -1);F.add(b[i], 1);G.add(b[i + 1], -1);}}trace(cnt);vector<ii> B;for (auto& [k, v] : cnt) if (v) B.push_back({k, v});int m = SZ(B);vector<int64> pre(m + 1);for (int i = 0; i < m; ++i) {pre[i + 1] = pre[i] + B[i].second;}int q;cin >> q;while (q--) {int64 ll, rr;cin >> ll >> rr;auto u = lower_bound(B.begin(), B.end(), ii{ll, 0LL}) - B.begin();auto v = lower_bound(B.begin(), B.end(), ii{rr + 1, 0LL}) - B.begin();cout << pre[v] - pre[u] << '\n';}return 0;}