oj.uz

Submission #758391

# Submission time Handle Problem Language Result Execution time Memory
758391 2023-06-14T14:35:05 Z groshi Fire (JOI20_ho_t5) C++17
100 / 100
 556 ms 187140 KB 
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long Int;
typedef pair<Int, Int> P;
#define LINF (1LL<<60)
 
const int Base = 220000;
struct BIT{
    int n;
    Int bit[Base * 2 + 1];
    BIT(Int n):n(n){}
 
    void add(int ind, Int val){
        ind += Base;
        while(ind < n){
            bit[ind] += val;
            ind += ind & -ind;
        }
    }
 
    Int sum(int ind){
        Int ans = 0;
        ind += Base;
        while(ind){
            ans += bit[ind];
            ind -= ind & -ind;
        }
        return ans;
    }
};
 
vector<P> task1[440000], task2[440000], task3[440000], task4[440000], task5[440000];
BIT bit1(440000), bit2(440000), bit3(440000), bit4(440000),bit5(440000);
 
Int calc(Int t, Int x){
    return (x-t) * (bit1.sum(x-t) + bit2.sum(x)) + (bit3.sum(x-t) + bit4.sum(x)) + t * bit5.sum(x);
}
 
void add_triangle(Int l, Int r, Int v){
    task1[0].emplace_back(l+1, v);
    task2[0].emplace_back(r, -v);
    task3[0].emplace_back(l+1, -l*v);
    task4[0].emplace_back(r, (r-1)*v);
    task5[0].emplace_back(r, -v);
    task1[r-l].emplace_back(l+1, -v);
    task2[r-l].emplace_back(r, v);
    task3[r-l].emplace_back(l+1, l*v);
    task4[r-l].emplace_back(r, -(r-1)*v);
    task5[r-l].emplace_back(r, v);
}
 
int a[Base], left[Base], right[Base];
int l[Base], r[Base];
Int ans[Base];
vector<int> query[Base];
vector<P> stk;
int n, q, t;
 
int main(){
    scanf("%d%d", &n, &q);
    for(Int i = 0;i < n;i++)scanf("%d", &a[i]);
 
    stk = {{LINF, -n-1}};
    for(Int i = 0;i < n;i++){
        while(stk.back().first <= a[i])stk.pop_back();
        ::left[i] = stk.back().second;
        stk.push_back({a[i], i});
    }
    stk = {{LINF, n+1}};
    for(Int i = n-1;i >= 0;i--){
        while(stk.back().first < a[i])stk.pop_back();
        ::right[i] = stk.back().second;
        stk.push_back({a[i], i});
    }
 
    for(Int i = 0;i < n;i++){
        add_triangle(::left[i], ::right[i], a[i]);
        add_triangle(::left[i], i, -a[i]);
        add_triangle(i, ::right[i], -a[i]);
    }
int prev = -1;
 
    for(Int i = 0;i < q;i++){
        scanf("%d%d%d", &t, &l[i], &r[i]);l[i]--,r[i]--;
if (prev != -1 && t != prev) {
throw;
}
        query[t].emplace_back(i);
    }
 
    for(Int t = 0;t <= n;t++){
        for(auto tmp: task1[t])bit1.add(tmp.first, tmp.second);
        for(auto tmp: task2[t])bit2.add(tmp.first, tmp.second);
        for(auto tmp: task3[t])bit3.add(tmp.first, tmp.second);
        for(auto tmp: task4[t])bit4.add(tmp.first, tmp.second);
        for(auto tmp: task5[t])bit5.add(tmp.first, tmp.second);
        
        for(Int i: query[t]){
            ans[i] = calc(t, r[i]) - calc(t, l[i]-1);
        }
    }
 
    for(int i = 0;i < q;i++)printf("%lld\n", ans[i]);
    return 0;
}

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:63:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     for(Int i = 0;i < n;i++)scanf("%d", &a[i]);
      |                             ~~~~~^~~~~~~~~~~~~
ho_t5.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d%d%d", &t, &l[i], &r[i]);l[i]--,r[i]--;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 57300 KB Output is correct
2 Correct 30 ms 57416 KB Output is correct
3 Correct 30 ms 57388 KB Output is correct
4 Correct 30 ms 57428 KB Output is correct
5 Correct 29 ms 57480 KB Output is correct
6 Correct 32 ms 57428 KB Output is correct
7 Correct 30 ms 57408 KB Output is correct
8 Correct 30 ms 57380 KB Output is correct
9 Correct 29 ms 57476 KB Output is correct
10 Correct 30 ms 57428 KB Output is correct
11 Correct 30 ms 57428 KB Output is correct
12 Correct 30 ms 57420 KB Output is correct
13 Correct 30 ms 57460 KB Output is correct
14 Correct 32 ms 57364 KB Output is correct
15 Correct 29 ms 57472 KB Output is correct
16 Correct 30 ms 57388 KB Output is correct
17 Correct 31 ms 57476 KB Output is correct
18 Correct 30 ms 57428 KB Output is correct
19 Correct 30 ms 57408 KB Output is correct
20 Correct 30 ms 57480 KB Output is correct
21 Correct 28 ms 57472 KB Output is correct
22 Correct 28 ms 57360 KB Output is correct
23 Correct 29 ms 57368 KB Output is correct
24 Correct 30 ms 57436 KB Output is correct
25 Correct 29 ms 57444 KB Output is correct
26 Correct 29 ms 57452 KB Output is correct
27 Correct 29 ms 57428 KB Output is correct
28 Correct 29 ms 57332 KB Output is correct
29 Correct 31 ms 57480 KB Output is correct
30 Correct 30 ms 57464 KB Output is correct
31 Correct 29 ms 57448 KB Output is correct
32 Correct 30 ms 57396 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 57300 KB Output is correct
2 Correct 384 ms 174300 KB Output is correct
3 Correct 377 ms 173620 KB Output is correct
4 Correct 377 ms 174716 KB Output is correct
5 Correct 379 ms 183628 KB Output is correct
6 Correct 394 ms 174308 KB Output is correct
7 Correct 440 ms 174992 KB Output is correct
8 Correct 390 ms 187140 KB Output is correct
9 Correct 371 ms 177732 KB Output is correct
10 Correct 358 ms 173136 KB Output is correct
11 Correct 368 ms 177972 KB Output is correct
12 Correct 357 ms 173392 KB Output is correct
13 Correct 383 ms 182720 KB Output is correct
14 Correct 368 ms 183160 KB Output is correct
15 Correct 391 ms 182452 KB Output is correct
16 Correct 388 ms 174704 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 57300 KB Output is correct
2 Correct 456 ms 175892 KB Output is correct
3 Correct 459 ms 173920 KB Output is correct
4 Correct 490 ms 183656 KB Output is correct
5 Correct 454 ms 174820 KB Output is correct
6 Correct 453 ms 175748 KB Output is correct
7 Correct 456 ms 180816 KB Output is correct
8 Correct 484 ms 174936 KB Output is correct
9 Correct 441 ms 174508 KB Output is correct
10 Correct 437 ms 173668 KB Output is correct
11 Correct 478 ms 184260 KB Output is correct
12 Correct 451 ms 182412 KB Output is correct
13 Correct 475 ms 183216 KB Output is correct
14 Correct 466 ms 174192 KB Output is correct
15 Correct 447 ms 184000 KB Output is correct
16 Correct 448 ms 183540 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 179044 KB Output is correct
2 Correct 477 ms 179528 KB Output is correct
3 Correct 496 ms 181936 KB Output is correct
4 Correct 476 ms 176868 KB Output is correct
5 Correct 459 ms 179232 KB Output is correct
6 Correct 460 ms 180776 KB Output is correct
7 Correct 474 ms 181552 KB Output is correct
8 Correct 488 ms 180704 KB Output is correct
9 Correct 468 ms 178628 KB Output is correct
10 Correct 461 ms 180184 KB Output is correct
11 Correct 459 ms 179368 KB Output is correct
12 Correct 476 ms 180488 KB Output is correct
13 Correct 470 ms 180172 KB Output is correct
14 Correct 477 ms 179212 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 57300 KB Output is correct
2 Correct 30 ms 57416 KB Output is correct
3 Correct 30 ms 57388 KB Output is correct
4 Correct 30 ms 57428 KB Output is correct
5 Correct 29 ms 57480 KB Output is correct
6 Correct 32 ms 57428 KB Output is correct
7 Correct 30 ms 57408 KB Output is correct
8 Correct 30 ms 57380 KB Output is correct
9 Correct 29 ms 57476 KB Output is correct
10 Correct 30 ms 57428 KB Output is correct
11 Correct 30 ms 57428 KB Output is correct
12 Correct 30 ms 57420 KB Output is correct
13 Correct 30 ms 57460 KB Output is correct
14 Correct 32 ms 57364 KB Output is correct
15 Correct 29 ms 57472 KB Output is correct
16 Correct 30 ms 57388 KB Output is correct
17 Correct 31 ms 57476 KB Output is correct
18 Correct 30 ms 57428 KB Output is correct
19 Correct 30 ms 57408 KB Output is correct
20 Correct 30 ms 57480 KB Output is correct
21 Correct 28 ms 57472 KB Output is correct
22 Correct 28 ms 57360 KB Output is correct
23 Correct 29 ms 57368 KB Output is correct
24 Correct 30 ms 57436 KB Output is correct
25 Correct 29 ms 57444 KB Output is correct
26 Correct 29 ms 57452 KB Output is correct
27 Correct 29 ms 57428 KB Output is correct
28 Correct 29 ms 57332 KB Output is correct
29 Correct 31 ms 57480 KB Output is correct
30 Correct 30 ms 57464 KB Output is correct
31 Correct 29 ms 57448 KB Output is correct
32 Correct 30 ms 57396 KB Output is correct
33 Correct 384 ms 174300 KB Output is correct
34 Correct 377 ms 173620 KB Output is correct
35 Correct 377 ms 174716 KB Output is correct
36 Correct 379 ms 183628 KB Output is correct
37 Correct 394 ms 174308 KB Output is correct
38 Correct 440 ms 174992 KB Output is correct
39 Correct 390 ms 187140 KB Output is correct
40 Correct 371 ms 177732 KB Output is correct
41 Correct 358 ms 173136 KB Output is correct
42 Correct 368 ms 177972 KB Output is correct
43 Correct 357 ms 173392 KB Output is correct
44 Correct 383 ms 182720 KB Output is correct
45 Correct 368 ms 183160 KB Output is correct
46 Correct 391 ms 182452 KB Output is correct
47 Correct 388 ms 174704 KB Output is correct
48 Correct 456 ms 175892 KB Output is correct
49 Correct 459 ms 173920 KB Output is correct
50 Correct 490 ms 183656 KB Output is correct
51 Correct 454 ms 174820 KB Output is correct
52 Correct 453 ms 175748 KB Output is correct
53 Correct 456 ms 180816 KB Output is correct
54 Correct 484 ms 174936 KB Output is correct
55 Correct 441 ms 174508 KB Output is correct
56 Correct 437 ms 173668 KB Output is correct
57 Correct 478 ms 184260 KB Output is correct
58 Correct 451 ms 182412 KB Output is correct
59 Correct 475 ms 183216 KB Output is correct
60 Correct 466 ms 174192 KB Output is correct
61 Correct 447 ms 184000 KB Output is correct
62 Correct 448 ms 183540 KB Output is correct
63 Correct 481 ms 179044 KB Output is correct
64 Correct 477 ms 179528 KB Output is correct
65 Correct 496 ms 181936 KB Output is correct
66 Correct 476 ms 176868 KB Output is correct
67 Correct 459 ms 179232 KB Output is correct
68 Correct 460 ms 180776 KB Output is correct
69 Correct 474 ms 181552 KB Output is correct
70 Correct 488 ms 180704 KB Output is correct
71 Correct 468 ms 178628 KB Output is correct
72 Correct 461 ms 180184 KB Output is correct
73 Correct 459 ms 179368 KB Output is correct
74 Correct 476 ms 180488 KB Output is correct
75 Correct 470 ms 180172 KB Output is correct
76 Correct 477 ms 179212 KB Output is correct
77 Correct 464 ms 175784 KB Output is correct
78 Correct 556 ms 177048 KB Output is correct
79 Correct 462 ms 184428 KB Output is correct
80 Correct 439 ms 175924 KB Output is correct
81 Correct 483 ms 175916 KB Output is correct
82 Correct 444 ms 177888 KB Output is correct
83 Correct 448 ms 176196 KB Output is correct
84 Correct 456 ms 174492 KB Output is correct
85 Correct 468 ms 184932 KB Output is correct
86 Correct 470 ms 175888 KB Output is correct
87 Correct 402 ms 184760 KB Output is correct
88 Correct 398 ms 183712 KB Output is correct
89 Correct 413 ms 172664 KB Output is correct
90 Correct 415 ms 183108 KB Output is correct
91 Correct 406 ms 173576 KB Output is correct
92 Correct 389 ms 171952 KB Output is correct
93 Correct 429 ms 174292 KB Output is correct
94 Correct 439 ms 183360 KB Output is correct
95 Correct 421 ms 183688 KB Output is correct
96 Correct 420 ms 174088 KB Output is correct
97 Correct 413 ms 174416 KB Output is correct
98 Correct 410 ms 173260 KB Output is correct
99 Correct 438 ms 177460 KB Output is correct
100 Correct 434 ms 177460 KB Output is correct
101 Correct 431 ms 173708 KB Output is correct
102 Correct 441 ms 183244 KB Output is correct