oj.uz

Submission #363488

# Submission time Handle Problem Language Result Execution time Memory
363488 2021-02-06T08:51:31 Z Lam_lai_cuoc_doi Fire (JOI20_ho_t5) C++17
14 / 100
 757 ms 262144 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#define task "A"
using namespace std;
using ll = long long;
using ld = long double;

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)
    {
        //cout << i << ": ";
        for (auto j : upd[i])
            f.Update(j.first, j.second);
        //for (int i = 1; i <= n; ++i)
        //    cout << f.Get(i, i) << " ";
        //cout << "\n";
        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_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    Solve();
}

Compilation message

ho_t5.cpp: In function 'int32_t main()':
ho_t5.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  109 |         freopen(task ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ho_t5.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  110 |         freopen(task ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11372 KB Output is correct
2 Correct 8 ms 11372 KB Output is correct
3 Correct 7 ms 11372 KB Output is correct
4 Correct 8 ms 11372 KB Output is correct
5 Correct 9 ms 11372 KB Output is correct
6 Correct 8 ms 11372 KB Output is correct
7 Correct 8 ms 11372 KB Output is correct
8 Correct 7 ms 11372 KB Output is correct
9 Correct 8 ms 11364 KB Output is correct
10 Correct 8 ms 11372 KB Output is correct
11 Correct 7 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 7 ms 11372 KB Output is correct
17 Correct 7 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 7 ms 11372 KB Output is correct
22 Correct 9 ms 11500 KB Output is correct
23 Correct 7 ms 11372 KB Output is correct
24 Correct 7 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 11500 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 405 ms 116752 KB Output is correct
3 Correct 373 ms 111272 KB Output is correct
4 Correct 380 ms 111704 KB Output is correct
5 Correct 382 ms 115692 KB Output is correct
6 Correct 420 ms 116620 KB Output is correct
7 Correct 358 ms 109612 KB Output is correct
8 Correct 384 ms 110448 KB Output is correct
9 Correct 407 ms 123720 KB Output is correct
10 Correct 421 ms 112984 KB Output is correct
11 Correct 426 ms 116456 KB Output is correct
12 Correct 387 ms 117924 KB Output is correct
13 Correct 361 ms 106320 KB Output is correct
14 Correct 412 ms 125768 KB Output is correct
15 Correct 393 ms 117968 KB Output is correct
16 Correct 409 ms 122604 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 468 ms 126452 KB Output is correct
3 Correct 440 ms 116784 KB Output is correct
4 Correct 511 ms 132316 KB Output is correct
5 Correct 447 ms 114096 KB Output is correct
6 Correct 442 ms 118428 KB Output is correct
7 Correct 432 ms 111016 KB Output is correct
8 Correct 425 ms 111316 KB Output is correct
9 Correct 419 ms 107824 KB Output is correct
10 Correct 420 ms 110624 KB Output is correct
11 Correct 458 ms 117528 KB Output is correct
12 Correct 463 ms 121476 KB Output is correct
13 Correct 482 ms 117796 KB Output is correct
14 Correct 429 ms 108444 KB Output is correct
15 Correct 461 ms 116668 KB Output is correct
16 Correct 435 ms 112168 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 757 ms 262144 KB Execution killed with signal 9
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 8 ms 11372 KB Output is correct
3 Correct 7 ms 11372 KB Output is correct
4 Correct 8 ms 11372 KB Output is correct
5 Correct 9 ms 11372 KB Output is correct
6 Correct 8 ms 11372 KB Output is correct
7 Correct 8 ms 11372 KB Output is correct
8 Correct 7 ms 11372 KB Output is correct
9 Correct 8 ms 11364 KB Output is correct
10 Correct 8 ms 11372 KB Output is correct
11 Correct 7 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 7 ms 11372 KB Output is correct
17 Correct 7 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 7 ms 11372 KB Output is correct
22 Correct 9 ms 11500 KB Output is correct
23 Correct 7 ms 11372 KB Output is correct
24 Correct 7 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 11500 KB Output is correct
33 Correct 405 ms 116752 KB Output is correct
34 Correct 373 ms 111272 KB Output is correct
35 Correct 380 ms 111704 KB Output is correct
36 Correct 382 ms 115692 KB Output is correct
37 Correct 420 ms 116620 KB Output is correct
38 Correct 358 ms 109612 KB Output is correct
39 Correct 384 ms 110448 KB Output is correct
40 Correct 407 ms 123720 KB Output is correct
41 Correct 421 ms 112984 KB Output is correct
42 Correct 426 ms 116456 KB Output is correct
43 Correct 387 ms 117924 KB Output is correct
44 Correct 361 ms 106320 KB Output is correct
45 Correct 412 ms 125768 KB Output is correct
46 Correct 393 ms 117968 KB Output is correct
47 Correct 409 ms 122604 KB Output is correct
48 Correct 468 ms 126452 KB Output is correct
49 Correct 440 ms 116784 KB Output is correct
50 Correct 511 ms 132316 KB Output is correct
51 Correct 447 ms 114096 KB Output is correct
52 Correct 442 ms 118428 KB Output is correct
53 Correct 432 ms 111016 KB Output is correct
54 Correct 425 ms 111316 KB Output is correct
55 Correct 419 ms 107824 KB Output is correct
56 Correct 420 ms 110624 KB Output is correct
57 Correct 458 ms 117528 KB Output is correct
58 Correct 463 ms 121476 KB Output is correct
59 Correct 482 ms 117796 KB Output is correct
60 Correct 429 ms 108444 KB Output is correct
61 Correct 461 ms 116668 KB Output is correct
62 Correct 435 ms 112168 KB Output is correct
63 Runtime error 757 ms 262144 KB Execution killed with signal 9
64 Halted 0 ms 0 KB -