oj.uz

Submission #531206

# Submission time Handle Problem Language Result Execution time Memory
531206 2022-02-28T04:52:17 Z Killer2501 Fire (JOI20_ho_t5) C++17
100 / 100
 412 ms 89616 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, ll>
#define fi first
#define se second
using namespace std;
const int N = 2e5+5;
const int M = 250;
const int mod = 1e9+7;
const ll base = 75;
const ll inf = 1e16;
ll n, t, lab[N], c[N], b[N], a[N];
ll ans, tong, d[N], l[N], r[N], fe[N];
ll m, k;
vector<pii> adj[N], radj[N];
vector<int> vi, ask[N];
string s, res;
struct node
{
    int l, r, t;
}q[N];
void add(int id, ll x)
{
    assert(id > 0);
    for(; id <= n; id += id & -id)fe[id] += x;
}
ll get(int id)
{
    ll total = 0;
    if(id <= 0)return total;
    for(; id; id -= id & -id)total += fe[id];
    return total;
}
void sol()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        while(!vi.empty() && a[i] >= a[vi.back()])vi.pop_back();
        l[i] = vi.empty() ? 0 : vi.back();
        vi.pb(i);
    }
    vi.clear();
    for(int i = n; i > 0; i --)
    {
        while(!vi.empty() && a[i] > a[vi.back()])vi.pop_back();
        r[i] = vi.empty() ? n+1 : vi.back();
        vi.pb(i);
    }
    for(int i = 1; i <= n; i ++)
    {
        //cout << l[i] <<" "<<r[i] << '\n';
        if(!l[i] || i-l[i] > r[i]-i)
        {
            for(int j = i; j < r[i]; j ++)
            {
                adj[j-i].pb({j, a[i]});
                if(l[i])adj[j-l[i]].pb({j, -a[i]});
            }
        }
        else
        {
            for(int j = i; j > l[i]; j --)
            {
                radj[i-j].pb({j, a[i]});
                if(r[i] <= n)radj[r[i]-j].pb({j, -a[i]});
            }
        }
    }
    for(int i = 1; i <= m; i ++)
    {
        cin >> q[i].t >> q[i].l >> q[i].r;
        ask[q[i].t].pb(i);
    }
    for(int i = 0; i <= n; i ++)
    {
        for(pii j: adj[i])add(j.fi, j.se);
        for(int j: ask[i])d[j] += get(q[j].r)-get(q[j].l-1);
    }
    fill_n(fe, n+1, 0);
    for(int i = 0; i <= n; i ++)
    {
        for(pii j: radj[i])add(j.fi, j.se);
        for(int j: ask[i])d[j] += get(q[j].r-i) - get(q[j].l-i-1);
    }
    for(int i = 1; i <= m; i ++)cout << d[i] << '\n';
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
    //cin >> test;
    while(test -- > 0)sol();
    return 0;
}

Compilation message

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14412 KB Output is correct
2 Correct 11 ms 14392 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 7 ms 14408 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 9 ms 14412 KB Output is correct
9 Correct 11 ms 14412 KB Output is correct
10 Correct 9 ms 14492 KB Output is correct
11 Correct 10 ms 14412 KB Output is correct
12 Correct 9 ms 14384 KB Output is correct
13 Correct 9 ms 14412 KB Output is correct
14 Correct 8 ms 14468 KB Output is correct
15 Correct 10 ms 14420 KB Output is correct
16 Correct 8 ms 14412 KB Output is correct
17 Correct 9 ms 14412 KB Output is correct
18 Correct 9 ms 14412 KB Output is correct
19 Correct 8 ms 14468 KB Output is correct
20 Correct 11 ms 14416 KB Output is correct
21 Correct 9 ms 14420 KB Output is correct
22 Correct 9 ms 14412 KB Output is correct
23 Correct 9 ms 14416 KB Output is correct
24 Correct 11 ms 14376 KB Output is correct
25 Correct 9 ms 14432 KB Output is correct
26 Correct 10 ms 14412 KB Output is correct
27 Correct 8 ms 14432 KB Output is correct
28 Correct 10 ms 14472 KB Output is correct
29 Correct 9 ms 14412 KB Output is correct
30 Correct 11 ms 14436 KB Output is correct
31 Correct 9 ms 14416 KB Output is correct
32 Correct 9 ms 14416 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14412 KB Output is correct
2 Correct 291 ms 77660 KB Output is correct
3 Correct 245 ms 83432 KB Output is correct
4 Correct 272 ms 79376 KB Output is correct
5 Correct 328 ms 82416 KB Output is correct
6 Correct 271 ms 81104 KB Output is correct
7 Correct 257 ms 79720 KB Output is correct
8 Correct 301 ms 82720 KB Output is correct
9 Correct 263 ms 81552 KB Output is correct
10 Correct 246 ms 78252 KB Output is correct
11 Correct 285 ms 78608 KB Output is correct
12 Correct 268 ms 78516 KB Output is correct
13 Correct 289 ms 80732 KB Output is correct
14 Correct 283 ms 81784 KB Output is correct
15 Correct 257 ms 82652 KB Output is correct
16 Correct 269 ms 86148 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14412 KB Output is correct
2 Correct 372 ms 85140 KB Output is correct
3 Correct 360 ms 80548 KB Output is correct
4 Correct 373 ms 89616 KB Output is correct
5 Correct 382 ms 80308 KB Output is correct
6 Correct 363 ms 81756 KB Output is correct
7 Correct 387 ms 81504 KB Output is correct
8 Correct 406 ms 82176 KB Output is correct
9 Correct 387 ms 80672 KB Output is correct
10 Correct 381 ms 83612 KB Output is correct
11 Correct 412 ms 86936 KB Output is correct
12 Correct 362 ms 83368 KB Output is correct
13 Correct 383 ms 85420 KB Output is correct
14 Correct 359 ms 78464 KB Output is correct
15 Correct 357 ms 83640 KB Output is correct
16 Correct 381 ms 83372 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 40252 KB Output is correct
2 Correct 221 ms 40320 KB Output is correct
3 Correct 263 ms 40752 KB Output is correct
4 Correct 261 ms 40468 KB Output is correct
5 Correct 215 ms 40356 KB Output is correct
6 Correct 209 ms 40272 KB Output is correct
7 Correct 182 ms 40692 KB Output is correct
8 Correct 218 ms 40652 KB Output is correct
9 Correct 195 ms 40248 KB Output is correct
10 Correct 228 ms 40448 KB Output is correct
11 Correct 182 ms 40652 KB Output is correct
12 Correct 220 ms 40628 KB Output is correct
13 Correct 201 ms 40444 KB Output is correct
14 Correct 199 ms 40608 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14412 KB Output is correct
2 Correct 11 ms 14392 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 7 ms 14408 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 9 ms 14412 KB Output is correct
9 Correct 11 ms 14412 KB Output is correct
10 Correct 9 ms 14492 KB Output is correct
11 Correct 10 ms 14412 KB Output is correct
12 Correct 9 ms 14384 KB Output is correct
13 Correct 9 ms 14412 KB Output is correct
14 Correct 8 ms 14468 KB Output is correct
15 Correct 10 ms 14420 KB Output is correct
16 Correct 8 ms 14412 KB Output is correct
17 Correct 9 ms 14412 KB Output is correct
18 Correct 9 ms 14412 KB Output is correct
19 Correct 8 ms 14468 KB Output is correct
20 Correct 11 ms 14416 KB Output is correct
21 Correct 9 ms 14420 KB Output is correct
22 Correct 9 ms 14412 KB Output is correct
23 Correct 9 ms 14416 KB Output is correct
24 Correct 11 ms 14376 KB Output is correct
25 Correct 9 ms 14432 KB Output is correct
26 Correct 10 ms 14412 KB Output is correct
27 Correct 8 ms 14432 KB Output is correct
28 Correct 10 ms 14472 KB Output is correct
29 Correct 9 ms 14412 KB Output is correct
30 Correct 11 ms 14436 KB Output is correct
31 Correct 9 ms 14416 KB Output is correct
32 Correct 9 ms 14416 KB Output is correct
33 Correct 291 ms 77660 KB Output is correct
34 Correct 245 ms 83432 KB Output is correct
35 Correct 272 ms 79376 KB Output is correct
36 Correct 328 ms 82416 KB Output is correct
37 Correct 271 ms 81104 KB Output is correct
38 Correct 257 ms 79720 KB Output is correct
39 Correct 301 ms 82720 KB Output is correct
40 Correct 263 ms 81552 KB Output is correct
41 Correct 246 ms 78252 KB Output is correct
42 Correct 285 ms 78608 KB Output is correct
43 Correct 268 ms 78516 KB Output is correct
44 Correct 289 ms 80732 KB Output is correct
45 Correct 283 ms 81784 KB Output is correct
46 Correct 257 ms 82652 KB Output is correct
47 Correct 269 ms 86148 KB Output is correct
48 Correct 372 ms 85140 KB Output is correct
49 Correct 360 ms 80548 KB Output is correct
50 Correct 373 ms 89616 KB Output is correct
51 Correct 382 ms 80308 KB Output is correct
52 Correct 363 ms 81756 KB Output is correct
53 Correct 387 ms 81504 KB Output is correct
54 Correct 406 ms 82176 KB Output is correct
55 Correct 387 ms 80672 KB Output is correct
56 Correct 381 ms 83612 KB Output is correct
57 Correct 412 ms 86936 KB Output is correct
58 Correct 362 ms 83368 KB Output is correct
59 Correct 383 ms 85420 KB Output is correct
60 Correct 359 ms 78464 KB Output is correct
61 Correct 357 ms 83640 KB Output is correct
62 Correct 381 ms 83372 KB Output is correct
63 Correct 214 ms 40252 KB Output is correct
64 Correct 221 ms 40320 KB Output is correct
65 Correct 263 ms 40752 KB Output is correct
66 Correct 261 ms 40468 KB Output is correct
67 Correct 215 ms 40356 KB Output is correct
68 Correct 209 ms 40272 KB Output is correct
69 Correct 182 ms 40692 KB Output is correct
70 Correct 218 ms 40652 KB Output is correct
71 Correct 195 ms 40248 KB Output is correct
72 Correct 228 ms 40448 KB Output is correct
73 Correct 182 ms 40652 KB Output is correct
74 Correct 220 ms 40628 KB Output is correct
75 Correct 201 ms 40444 KB Output is correct
76 Correct 199 ms 40608 KB Output is correct
77 Correct 314 ms 85376 KB Output is correct
78 Correct 363 ms 85340 KB Output is correct
79 Correct 338 ms 86824 KB Output is correct
80 Correct 325 ms 86524 KB Output is correct
81 Correct 320 ms 86812 KB Output is correct
82 Correct 335 ms 87076 KB Output is correct
83 Correct 341 ms 85188 KB Output is correct
84 Correct 346 ms 82312 KB Output is correct
85 Correct 309 ms 85652 KB Output is correct
86 Correct 330 ms 87112 KB Output is correct
87 Correct 260 ms 85684 KB Output is correct
88 Correct 300 ms 80004 KB Output is correct
89 Correct 245 ms 78876 KB Output is correct
90 Correct 272 ms 84036 KB Output is correct
91 Correct 278 ms 84308 KB Output is correct
92 Correct 251 ms 80808 KB Output is correct
93 Correct 271 ms 85720 KB Output is correct
94 Correct 313 ms 84096 KB Output is correct
95 Correct 305 ms 84812 KB Output is correct
96 Correct 272 ms 85244 KB Output is correct
97 Correct 291 ms 85364 KB Output is correct
98 Correct 291 ms 82616 KB Output is correct
99 Correct 307 ms 82324 KB Output is correct
100 Correct 292 ms 86696 KB Output is correct
101 Correct 319 ms 80664 KB Output is correct
102 Correct 281 ms 81640 KB Output is correct