#1063641 (C++14) No.1975 Zigzag Sequence

• 問題: No.1975 Zigzag Sequence
• ユーザー: RiRinbaru
• 提出日時: 2025-04-04 03:28:29
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 145 ms / 2,000 ms
• コード長: 2,450 bytes
• コンパイル時間: 4,026 ms
• コンパイル使用メモリ: 234,792 KB
• 実行使用メモリ: 15,816 KB
• 最終ジャッジ日時: 2025-04-04 03:28:38
• 合計ジャッジ時間: 9,178 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 33

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
#define rep(i, p, n) for (ll i = p; i < (ll)(n); i++)
#define rep2(i, p, n) for (ll i = p; i >= (ll)(n); i--)
using namespace std;
using ll = long long;
using ld = long double;
const double pi = 3.141592653589793;
const long long inf = 2 * 1e9;
const long long linf = 4 * 1e18;
const ll mod1 = 1000000007;
const ll mod2 = 998244353;
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
// atcoder
#include <atcoder/all>
using namespace atcoder;
using mint1 = modint1000000007;
using mint2 = modint998244353;
vector<pair<ll, ll>> base = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<mint1> li;
struct D
{
    mint1 num;
    ll co;
};
D op(D a, D b)
{
    return {b.num * li.at(a.co) + a.num, a.co + b.co};
}
D e()
{
    return {0, 0};
}
int main()
{
    //////////////////
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //////////////////
    ll N;
    cin >> N;
    li.push_back(1);
    rep(i, 0, 101010)
    {
        li.push_back(li.back() * 2);
    }
    vector<pair<ll, ll>> A(N);
    rep(i, 0, N)
    {
        ll B;
        cin >> B;
        A.at(i) = {B, i};
    }
    sort(A.begin(), A.end());
    mint1 ans = 0;
    vector<D> init(N, {0, 1});
    rep(i, 0, 2)
    {
        segtree<D, op, e> Lseg(init), Rseg(init);
        queue<ll> Q;
        ll now = -1;
        rep(i, 0, N)
        {
            if (A.at(i).first != now)
            {
                now = A.at(i).first;
                while (Q.size())
                {
                    ll P = Q.front();
                    Q.pop();
                    Lseg.set(P, {1, 1});
                    Rseg.set(N - 1 - P, {1, 1});
                }
            }
            // rep(i, 0, N)
            // {
            //     cout << Lseg.get(i).num.val();
            // }
            // cout << endl;
            // cout << Lseg.prod(0, A.at(i).second).num.val() << Rseg.prod(0, N - A.at(i).second).num.val() << endl;
            ans += Lseg.prod(0, A.at(i).second).num * Rseg.prod(0, N - A.at(i).second).num;
            Q.push(A.at(i).second);
        }
        rep(i, 0, N)
        {
            A.at(i).first = inf - A.at(i).first;
        }
        sort(A.begin(), A.end());
    }
    cout << ans.val() << endl;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX