oj.uz

Submission #363455

# Submission time Handle Problem Language Result Execution time Memory
363455 2021-02-06T05:14:37 Z Lam_lai_cuoc_doi Fire (JOI20_ho_t5) C++17
14 / 100
 501 ms 132176 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const bool typetest = 0;
const int N = 2e5 + 5;
struct FenwickTree
{
    ll a[N];
    int n;
    FenwickTree()
    {
        memset(a, 0, sizeof a);
    }
    void Clear()
    {
        memset(a, 0, sizeof a);
    }
    void Update(int p, ll v)
    {
        for (; p <= n; p += p & -p)
            a[p] += v;
    }
    ll Get(int p)
    {
        ll ans(0);
        for (; p > 0; p -= p & -p)
            ans += a[p];
        return ans;
    }
    ll Get(int l, int r)
    {
        return Get(r) - Get(l - 1);
    }
} f;
int n, pre[N], suf[N], q;
ll a[N], ans[N];
vector<pair<pair<int, int>, int>> que[N];
vector<pair<int, ll>> upd[N];

void Read()
{
    cin >> n >> q;
    f.n = n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= q; ++i)
    {
        int t, l, r;
        cin >> t >> l >> r;
        que[t].push_back({{l, r}, i});
    }
}

void Solve()
{
    vector<int> s;
    s.reserve(n);
    for (int i = 1; i <= n; ++i)
    {
        while (s.size() && a[s.back()] < a[i])
            s.pop_back();
        pre[i] = s.empty() ? 0 : s.back();
        s.push_back(i);
    }
    s.clear();
    for (int i = n; i; --i)
    {
        while (s.size() && a[s.back()] < a[i])
            s.pop_back();
        suf[i] = s.empty() ? n + 1 : s.back();
        s.push_back(i);
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = i; j < suf[i]; ++j)
        {
            upd[j - i].push_back({j, a[i]});
            if (pre[i])
                upd[j - pre[i]].push_back({j, -a[i]});
        }
    }
    for (int i = 0; i <= n; ++i)
    {
        for (auto j : upd[i])
            f.Update(j.first, j.second);
        for (auto j : que[i])
            ans[j.second] = f.Get(j.first.first, j.first.second);
    }
    for (int i = 1; i <= q; ++i)
        cout << ans[i] << "\n";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11372 KB Output is correct
2 Correct 9 ms 11372 KB Output is correct
3 Correct 9 ms 11372 KB Output is correct
4 Correct 8 ms 11372 KB Output is correct
5 Correct 8 ms 11372 KB Output is correct
6 Correct 8 ms 11372 KB Output is correct
7 Correct 8 ms 11368 KB Output is correct
8 Correct 8 ms 11372 KB Output is correct
9 Correct 8 ms 11372 KB Output is correct
10 Correct 8 ms 11372 KB Output is correct
11 Correct 8 ms 11372 KB Output is correct
12 Correct 8 ms 11372 KB Output is correct
13 Correct 8 ms 11372 KB Output is correct
14 Correct 8 ms 11372 KB Output is correct
15 Correct 8 ms 11372 KB Output is correct
16 Correct 8 ms 11372 KB Output is correct
17 Correct 8 ms 11372 KB Output is correct
18 Correct 8 ms 11372 KB Output is correct
19 Correct 8 ms 11372 KB Output is correct
20 Correct 8 ms 11372 KB Output is correct
21 Correct 8 ms 11372 KB Output is correct
22 Correct 8 ms 11372 KB Output is correct
23 Correct 8 ms 11372 KB Output is correct
24 Correct 8 ms 11372 KB Output is correct
25 Correct 8 ms 11372 KB Output is correct
26 Correct 8 ms 11372 KB Output is correct
27 Correct 8 ms 11372 KB Output is correct
28 Correct 8 ms 11372 KB Output is correct
29 Correct 8 ms 11372 KB Output is correct
30 Correct 8 ms 11372 KB Output is correct
31 Correct 8 ms 11372 KB Output is correct
32 Correct 8 ms 11372 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11372 KB Output is correct
2 Correct 392 ms 116820 KB Output is correct
3 Correct 371 ms 111328 KB Output is correct
4 Correct 373 ms 111828 KB Output is correct
5 Correct 385 ms 115788 KB Output is correct
6 Correct 379 ms 116436 KB Output is correct
7 Correct 366 ms 109780 KB Output is correct
8 Correct 371 ms 110452 KB Output is correct
9 Correct 409 ms 123708 KB Output is correct
10 Correct 369 ms 113108 KB Output is correct
11 Correct 389 ms 116504 KB Output is correct
12 Correct 389 ms 117716 KB Output is correct
13 Correct 362 ms 106316 KB Output is correct
14 Correct 417 ms 126012 KB Output is correct
15 Correct 400 ms 118256 KB Output is correct
16 Correct 411 ms 122552 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11372 KB Output is correct
2 Correct 489 ms 126484 KB Output is correct
3 Correct 438 ms 116656 KB Output is correct
4 Correct 501 ms 132176 KB Output is correct
5 Correct 442 ms 113960 KB Output is correct
6 Correct 457 ms 118348 KB Output is correct
7 Correct 419 ms 111140 KB Output is correct
8 Correct 438 ms 111480 KB Output is correct
9 Correct 404 ms 107712 KB Output is correct
10 Correct 426 ms 110840 KB Output is correct
11 Correct 458 ms 117504 KB Output is correct
12 Correct 455 ms 121408 KB Output is correct
13 Correct 450 ms 117760 KB Output is correct
14 Correct 410 ms 108700 KB Output is correct
15 Correct 441 ms 116816 KB Output is correct
16 Correct 439 ms 112244 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 186 ms 36276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11372 KB Output is correct
2 Correct 9 ms 11372 KB Output is correct
3 Correct 9 ms 11372 KB Output is correct
4 Correct 8 ms 11372 KB Output is correct
5 Correct 8 ms 11372 KB Output is correct
6 Correct 8 ms 11372 KB Output is correct
7 Correct 8 ms 11368 KB Output is correct
8 Correct 8 ms 11372 KB Output is correct
9 Correct 8 ms 11372 KB Output is correct
10 Correct 8 ms 11372 KB Output is correct
11 Correct 8 ms 11372 KB Output is correct
12 Correct 8 ms 11372 KB Output is correct
13 Correct 8 ms 11372 KB Output is correct
14 Correct 8 ms 11372 KB Output is correct
15 Correct 8 ms 11372 KB Output is correct
16 Correct 8 ms 11372 KB Output is correct
17 Correct 8 ms 11372 KB Output is correct
18 Correct 8 ms 11372 KB Output is correct
19 Correct 8 ms 11372 KB Output is correct
20 Correct 8 ms 11372 KB Output is correct
21 Correct 8 ms 11372 KB Output is correct
22 Correct 8 ms 11372 KB Output is correct
23 Correct 8 ms 11372 KB Output is correct
24 Correct 8 ms 11372 KB Output is correct
25 Correct 8 ms 11372 KB Output is correct
26 Correct 8 ms 11372 KB Output is correct
27 Correct 8 ms 11372 KB Output is correct
28 Correct 8 ms 11372 KB Output is correct
29 Correct 8 ms 11372 KB Output is correct
30 Correct 8 ms 11372 KB Output is correct
31 Correct 8 ms 11372 KB Output is correct
32 Correct 8 ms 11372 KB Output is correct
33 Correct 392 ms 116820 KB Output is correct
34 Correct 371 ms 111328 KB Output is correct
35 Correct 373 ms 111828 KB Output is correct
36 Correct 385 ms 115788 KB Output is correct
37 Correct 379 ms 116436 KB Output is correct
38 Correct 366 ms 109780 KB Output is correct
39 Correct 371 ms 110452 KB Output is correct
40 Correct 409 ms 123708 KB Output is correct
41 Correct 369 ms 113108 KB Output is correct
42 Correct 389 ms 116504 KB Output is correct
43 Correct 389 ms 117716 KB Output is correct
44 Correct 362 ms 106316 KB Output is correct
45 Correct 417 ms 126012 KB Output is correct
46 Correct 400 ms 118256 KB Output is correct
47 Correct 411 ms 122552 KB Output is correct
48 Correct 489 ms 126484 KB Output is correct
49 Correct 438 ms 116656 KB Output is correct
50 Correct 501 ms 132176 KB Output is correct
51 Correct 442 ms 113960 KB Output is correct
52 Correct 457 ms 118348 KB Output is correct
53 Correct 419 ms 111140 KB Output is correct
54 Correct 438 ms 111480 KB Output is correct
55 Correct 404 ms 107712 KB Output is correct
56 Correct 426 ms 110840 KB Output is correct
57 Correct 458 ms 117504 KB Output is correct
58 Correct 455 ms 121408 KB Output is correct
59 Correct 450 ms 117760 KB Output is correct
60 Correct 410 ms 108700 KB Output is correct
61 Correct 441 ms 116816 KB Output is correct
62 Correct 439 ms 112244 KB Output is correct
63 Incorrect 186 ms 36276 KB Output isn't correct
64 Halted 0 ms 0 KB -