oj.uz

Submission #813362

# Submission time Handle Problem Language Result Execution time Memory
813362 2023-08-07T16:22:25 Z 1075508020060209tc Fire (JOI20_ho_t5) C++14
100 / 100
 743 ms 133772 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int lowbit(int x){return x&-x;}
struct STBIT{
vector<int>bit;
int MXN;
void init(int x){
for(int i=0;i<=x+10;i++){
    bit.push_back(0);
}
MXN=x;
}
void upd(int pl,int vl){
    while(pl<=MXN){
        bit[pl]+=vl;
        pl+=lowbit(pl);
    }
}
int qsum(int pl){
if(pl<=0){return 0;}
int ret=0;
while(pl){
    ret+=bit[pl];
    pl-=lowbit(pl);
}
return ret;
}
};
struct tri{
int a;int b;int c;
};
int ar[1000006];
int lar[1000006];
int rar[1000006];
vector<tri>event[1000006];
int ans[1000006];
vector<pair<int,int>>qry[1000006];
STBIT mnf;
STBIT mns;
STBIT mnf2;
STBIT mns2;
int n;int Q;
void parallelogram(int i,int l,int r){
event[0].push_back({i-1+1,i,ar[i]});
if(r&&l){
    event[r-i].push_back({r-1+1,i,-ar[i]});
    event[i-l].push_back({i-1+1,l,-ar[i]});
    event[r-i+i-l].push_back({r-1+1,l,ar[i]});
    return;
}
if(r){
    event[r-i].push_back({r-1+1,i,-ar[i]});
    return;
}
if(l){
    event[i-l].push_back({i-1+1,l,-ar[i]});
    return;
}
}

void init(){
cin>>n>>Q;
n+=2;
for(int i=3;i<=n;i++){
    cin>>ar[i];
}
for(int i=1;i<=Q;i++){
    int t;int l;int r;
    cin>>t>>l>>r;
    l+=2;r+=2;
    qry[t].push_back({i,r});
    qry[t].push_back({i,-(l-1)});
}

stack<int>stk;
for(int i=3;i<=n;i++){
    while(stk.size()&&ar[stk.top()]<=ar[i]){stk.pop();}
    if(stk.size()){
        lar[i]=stk.top();
    }
    stk.push(i);
}
while(stk.size()){stk.pop();}
for(int i=n;i>=3;i--){
    while(stk.size()&&ar[stk.top()]<ar[i]){stk.pop();}
    if(stk.size()){
        rar[i]=stk.top();
    }
    stk.push(i);
}
for(int i=3;i<=n;i++){
    parallelogram(i,lar[i],rar[i]);
}
}



signed main() {
cin.tie(0);
ios_base::sync_with_stdio(0);

init();
mnf.init(1000000);
mns.init(1000000);
mnf2.init(1000000);
mns2.init(1000000);

for(int t=0;t<=1000000;t++){
    //    cout<<t<<":\n";
    for(int i=0;i<event[t].size();i++){
        int c;int a;int b;
        c=event[t][i].c;b=event[t][i].b;a=event[t][i].a;
        mnf.upd(b,c);
        mns.upd(b,b*c);
        mnf2.upd(a-1,c);
        mns2.upd(a-1, (a-1)*c);
      //  cout<<a<<" "<<b<<" "<<c<<endl;
    }

    for(int i=0;i<qry[t].size();i++){
        int id=qry[t][i].first;
        int p=qry[t][i].second;
        p=abs(p);
        int cal=t*mnf.qsum(1000000);
     //   cout<<p<<" "<<p-t<<"  ";
       // cout<<cal<<" ";
        cal+=mns.qsum(p-t)+(mnf.qsum(1000000)-mnf.qsum(p-t))*(p-t);
       // cout<<cal<<" ";
        cal-=mns2.qsum(p)+(mnf2.qsum(1000000)-mnf2.qsum(p))*(p);
       // cout<<cal<<" ";
        if(qry[t][i].second<0){
            ans[id]-=cal;
        }else{
            ans[id]+=cal;
        }
        //cout<<id<<" "<<ans[id]<<"\n";
    }
   // cout<<endl;
}
for(int i=1;i<=Q;i++){
    cout<<ans[i]<<endl;
}

}

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:115:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<tri>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i=0;i<event[t].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
ho_t5.cpp:125:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i=0;i<qry[t].size();i++){
      |                 ~^~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 83100 KB Output is correct
2 Correct 55 ms 83188 KB Output is correct
3 Correct 57 ms 83192 KB Output is correct
4 Correct 58 ms 83132 KB Output is correct
5 Correct 55 ms 83140 KB Output is correct
6 Correct 54 ms 83196 KB Output is correct
7 Correct 55 ms 83144 KB Output is correct
8 Correct 55 ms 83100 KB Output is correct
9 Correct 65 ms 83132 KB Output is correct
10 Correct 56 ms 83164 KB Output is correct
11 Correct 57 ms 83192 KB Output is correct
12 Correct 56 ms 83116 KB Output is correct
13 Correct 55 ms 83104 KB Output is correct
14 Correct 55 ms 83188 KB Output is correct
15 Correct 55 ms 83212 KB Output is correct
16 Correct 56 ms 83188 KB Output is correct
17 Correct 56 ms 83124 KB Output is correct
18 Correct 55 ms 83132 KB Output is correct
19 Correct 57 ms 83144 KB Output is correct
20 Correct 56 ms 83176 KB Output is correct
21 Correct 63 ms 83096 KB Output is correct
22 Correct 55 ms 83144 KB Output is correct
23 Correct 62 ms 83136 KB Output is correct
24 Correct 56 ms 83220 KB Output is correct
25 Correct 55 ms 83204 KB Output is correct
26 Correct 55 ms 83224 KB Output is correct
27 Correct 55 ms 83192 KB Output is correct
28 Correct 61 ms 83316 KB Output is correct
29 Correct 57 ms 83200 KB Output is correct
30 Correct 55 ms 83128 KB Output is correct
31 Correct 56 ms 83120 KB Output is correct
32 Correct 56 ms 83140 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 83100 KB Output is correct
2 Correct 559 ms 125052 KB Output is correct
3 Correct 538 ms 128428 KB Output is correct
4 Correct 589 ms 130996 KB Output is correct
5 Correct 586 ms 133772 KB Output is correct
6 Correct 554 ms 130272 KB Output is correct
7 Correct 598 ms 130808 KB Output is correct
8 Correct 594 ms 130876 KB Output is correct
9 Correct 602 ms 131352 KB Output is correct
10 Correct 580 ms 128108 KB Output is correct
11 Correct 590 ms 131572 KB Output is correct
12 Correct 581 ms 130292 KB Output is correct
13 Correct 622 ms 129144 KB Output is correct
14 Correct 588 ms 133388 KB Output is correct
15 Correct 591 ms 128496 KB Output is correct
16 Correct 558 ms 130884 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 83100 KB Output is correct
2 Correct 614 ms 123428 KB Output is correct
3 Correct 619 ms 128332 KB Output is correct
4 Correct 634 ms 130164 KB Output is correct
5 Correct 613 ms 128384 KB Output is correct
6 Correct 626 ms 128668 KB Output is correct
7 Correct 599 ms 128972 KB Output is correct
8 Correct 638 ms 128916 KB Output is correct
9 Correct 629 ms 128452 KB Output is correct
10 Correct 631 ms 127884 KB Output is correct
11 Correct 639 ms 129196 KB Output is correct
12 Correct 611 ms 128744 KB Output is correct
13 Correct 636 ms 129876 KB Output is correct
14 Correct 625 ms 121280 KB Output is correct
15 Correct 618 ms 129704 KB Output is correct
16 Correct 638 ms 129420 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 116860 KB Output is correct
2 Correct 521 ms 122128 KB Output is correct
3 Correct 545 ms 123116 KB Output is correct
4 Correct 593 ms 121544 KB Output is correct
5 Correct 606 ms 122788 KB Output is correct
6 Correct 574 ms 121876 KB Output is correct
7 Correct 507 ms 121960 KB Output is correct
8 Correct 547 ms 123228 KB Output is correct
9 Correct 567 ms 121504 KB Output is correct
10 Correct 590 ms 121324 KB Output is correct
11 Correct 585 ms 121572 KB Output is correct
12 Correct 566 ms 122680 KB Output is correct
13 Correct 604 ms 121960 KB Output is correct
14 Correct 595 ms 122692 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 83100 KB Output is correct
2 Correct 55 ms 83188 KB Output is correct
3 Correct 57 ms 83192 KB Output is correct
4 Correct 58 ms 83132 KB Output is correct
5 Correct 55 ms 83140 KB Output is correct
6 Correct 54 ms 83196 KB Output is correct
7 Correct 55 ms 83144 KB Output is correct
8 Correct 55 ms 83100 KB Output is correct
9 Correct 65 ms 83132 KB Output is correct
10 Correct 56 ms 83164 KB Output is correct
11 Correct 57 ms 83192 KB Output is correct
12 Correct 56 ms 83116 KB Output is correct
13 Correct 55 ms 83104 KB Output is correct
14 Correct 55 ms 83188 KB Output is correct
15 Correct 55 ms 83212 KB Output is correct
16 Correct 56 ms 83188 KB Output is correct
17 Correct 56 ms 83124 KB Output is correct
18 Correct 55 ms 83132 KB Output is correct
19 Correct 57 ms 83144 KB Output is correct
20 Correct 56 ms 83176 KB Output is correct
21 Correct 63 ms 83096 KB Output is correct
22 Correct 55 ms 83144 KB Output is correct
23 Correct 62 ms 83136 KB Output is correct
24 Correct 56 ms 83220 KB Output is correct
25 Correct 55 ms 83204 KB Output is correct
26 Correct 55 ms 83224 KB Output is correct
27 Correct 55 ms 83192 KB Output is correct
28 Correct 61 ms 83316 KB Output is correct
29 Correct 57 ms 83200 KB Output is correct
30 Correct 55 ms 83128 KB Output is correct
31 Correct 56 ms 83120 KB Output is correct
32 Correct 56 ms 83140 KB Output is correct
33 Correct 559 ms 125052 KB Output is correct
34 Correct 538 ms 128428 KB Output is correct
35 Correct 589 ms 130996 KB Output is correct
36 Correct 586 ms 133772 KB Output is correct
37 Correct 554 ms 130272 KB Output is correct
38 Correct 598 ms 130808 KB Output is correct
39 Correct 594 ms 130876 KB Output is correct
40 Correct 602 ms 131352 KB Output is correct
41 Correct 580 ms 128108 KB Output is correct
42 Correct 590 ms 131572 KB Output is correct
43 Correct 581 ms 130292 KB Output is correct
44 Correct 622 ms 129144 KB Output is correct
45 Correct 588 ms 133388 KB Output is correct
46 Correct 591 ms 128496 KB Output is correct
47 Correct 558 ms 130884 KB Output is correct
48 Correct 614 ms 123428 KB Output is correct
49 Correct 619 ms 128332 KB Output is correct
50 Correct 634 ms 130164 KB Output is correct
51 Correct 613 ms 128384 KB Output is correct
52 Correct 626 ms 128668 KB Output is correct
53 Correct 599 ms 128972 KB Output is correct
54 Correct 638 ms 128916 KB Output is correct
55 Correct 629 ms 128452 KB Output is correct
56 Correct 631 ms 127884 KB Output is correct
57 Correct 639 ms 129196 KB Output is correct
58 Correct 611 ms 128744 KB Output is correct
59 Correct 636 ms 129876 KB Output is correct
60 Correct 625 ms 121280 KB Output is correct
61 Correct 618 ms 129704 KB Output is correct
62 Correct 638 ms 129420 KB Output is correct
63 Correct 551 ms 116860 KB Output is correct
64 Correct 521 ms 122128 KB Output is correct
65 Correct 545 ms 123116 KB Output is correct
66 Correct 593 ms 121544 KB Output is correct
67 Correct 606 ms 122788 KB Output is correct
68 Correct 574 ms 121876 KB Output is correct
69 Correct 507 ms 121960 KB Output is correct
70 Correct 547 ms 123228 KB Output is correct
71 Correct 567 ms 121504 KB Output is correct
72 Correct 590 ms 121324 KB Output is correct
73 Correct 585 ms 121572 KB Output is correct
74 Correct 566 ms 122680 KB Output is correct
75 Correct 604 ms 121960 KB Output is correct
76 Correct 595 ms 122692 KB Output is correct
77 Correct 743 ms 129676 KB Output is correct
78 Correct 658 ms 122260 KB Output is correct
79 Correct 656 ms 130524 KB Output is correct
80 Correct 663 ms 129536 KB Output is correct
81 Correct 618 ms 121372 KB Output is correct
82 Correct 632 ms 130636 KB Output is correct
83 Correct 628 ms 121572 KB Output is correct
84 Correct 574 ms 121420 KB Output is correct
85 Correct 643 ms 130468 KB Output is correct
86 Correct 622 ms 129704 KB Output is correct
87 Correct 587 ms 132236 KB Output is correct
88 Correct 626 ms 132136 KB Output is correct
89 Correct 543 ms 130404 KB Output is correct
90 Correct 619 ms 131804 KB Output is correct
91 Correct 583 ms 122544 KB Output is correct
92 Correct 557 ms 130272 KB Output is correct
93 Correct 603 ms 130784 KB Output is correct
94 Correct 552 ms 132408 KB Output is correct
95 Correct 559 ms 132236 KB Output is correct
96 Correct 658 ms 122936 KB Output is correct
97 Correct 645 ms 130984 KB Output is correct
98 Correct 587 ms 130220 KB Output is correct
99 Correct 624 ms 131008 KB Output is correct
100 Correct 640 ms 131484 KB Output is correct
101 Correct 612 ms 130312 KB Output is correct
102 Correct 606 ms 131820 KB Output is correct