oj.uz

Submission #813363

# Submission time Handle Problem Language Result Execution time Memory
813363 2023-08-07T16:22:58 Z 1075508020060209tc Fire (JOI20_ho_t5) C++14
14 / 100
 731 ms 128648 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 65 ms 83104 KB Output is correct
2 Correct 77 ms 83216 KB Output is correct
3 Correct 56 ms 83200 KB Output is correct
4 Correct 58 ms 83132 KB Output is correct
5 Correct 65 ms 83092 KB Output is correct
6 Correct 57 ms 83176 KB Output is correct
7 Correct 59 ms 83108 KB Output is correct
8 Correct 57 ms 83104 KB Output is correct
9 Correct 67 ms 83132 KB Output is correct
10 Correct 61 ms 83132 KB Output is correct
11 Correct 56 ms 83108 KB Output is correct
12 Correct 55 ms 83216 KB Output is correct
13 Correct 66 ms 83180 KB Output is correct
14 Correct 70 ms 83124 KB Output is correct
15 Correct 66 ms 83212 KB Output is correct
16 Correct 63 ms 83204 KB Output is correct
17 Correct 55 ms 83124 KB Output is correct
18 Correct 72 ms 83188 KB Output is correct
19 Correct 59 ms 83140 KB Output is correct
20 Correct 57 ms 83208 KB Output is correct
21 Correct 76 ms 83116 KB Output is correct
22 Correct 66 ms 83112 KB Output is correct
23 Correct 72 ms 83120 KB Output is correct
24 Correct 54 ms 83232 KB Output is correct
25 Correct 53 ms 83084 KB Output is correct
26 Correct 54 ms 83124 KB Output is correct
27 Correct 66 ms 83116 KB Output is correct
28 Correct 61 ms 83124 KB Output is correct
29 Correct 53 ms 83124 KB Output is correct
30 Correct 57 ms 83140 KB Output is correct
31 Correct 56 ms 83112 KB Output is correct
32 Correct 70 ms 83244 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 83104 KB Output is correct
2 Correct 613 ms 125560 KB Output is correct
3 Correct 609 ms 123072 KB Output is correct
4 Correct 608 ms 125960 KB Output is correct
5 Correct 586 ms 128648 KB Output is correct
6 Correct 596 ms 125416 KB Output is correct
7 Correct 606 ms 125872 KB Output is correct
8 Correct 539 ms 125904 KB Output is correct
9 Correct 582 ms 126368 KB Output is correct
10 Correct 558 ms 123044 KB Output is correct
11 Correct 638 ms 126432 KB Output is correct
12 Correct 517 ms 125216 KB Output is correct
13 Correct 663 ms 124088 KB Output is correct
14 Correct 600 ms 128356 KB Output is correct
15 Correct 567 ms 123592 KB Output is correct
16 Correct 597 ms 126036 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 83104 KB Output is correct
2 Correct 614 ms 124176 KB Output is correct
3 Correct 619 ms 123468 KB Output is correct
4 Correct 731 ms 125060 KB Output is correct
5 Correct 674 ms 123740 KB Output is correct
6 Correct 692 ms 124048 KB Output is correct
7 Correct 589 ms 124264 KB Output is correct
8 Correct 659 ms 124088 KB Output is correct
9 Correct 640 ms 123700 KB Output is correct
10 Correct 601 ms 123372 KB Output is correct
11 Correct 659 ms 124492 KB Output is correct
12 Correct 646 ms 124048 KB Output is correct
13 Correct 645 ms 125112 KB Output is correct
14 Correct 636 ms 116648 KB Output is correct
15 Correct 660 ms 125200 KB Output is correct
16 Correct 607 ms 124952 KB Output is correct

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 83104 KB Output is correct
2 Correct 77 ms 83216 KB Output is correct
3 Correct 56 ms 83200 KB Output is correct
4 Correct 58 ms 83132 KB Output is correct
5 Correct 65 ms 83092 KB Output is correct
6 Correct 57 ms 83176 KB Output is correct
7 Correct 59 ms 83108 KB Output is correct
8 Correct 57 ms 83104 KB Output is correct
9 Correct 67 ms 83132 KB Output is correct
10 Correct 61 ms 83132 KB Output is correct
11 Correct 56 ms 83108 KB Output is correct
12 Correct 55 ms 83216 KB Output is correct
13 Correct 66 ms 83180 KB Output is correct
14 Correct 70 ms 83124 KB Output is correct
15 Correct 66 ms 83212 KB Output is correct
16 Correct 63 ms 83204 KB Output is correct
17 Correct 55 ms 83124 KB Output is correct
18 Correct 72 ms 83188 KB Output is correct
19 Correct 59 ms 83140 KB Output is correct
20 Correct 57 ms 83208 KB Output is correct
21 Correct 76 ms 83116 KB Output is correct
22 Correct 66 ms 83112 KB Output is correct
23 Correct 72 ms 83120 KB Output is correct
24 Correct 54 ms 83232 KB Output is correct
25 Correct 53 ms 83084 KB Output is correct
26 Correct 54 ms 83124 KB Output is correct
27 Correct 66 ms 83116 KB Output is correct
28 Correct 61 ms 83124 KB Output is correct
29 Correct 53 ms 83124 KB Output is correct
30 Correct 57 ms 83140 KB Output is correct
31 Correct 56 ms 83112 KB Output is correct
32 Correct 70 ms 83244 KB Output is correct
33 Correct 613 ms 125560 KB Output is correct
34 Correct 609 ms 123072 KB Output is correct
35 Correct 608 ms 125960 KB Output is correct
36 Correct 586 ms 128648 KB Output is correct
37 Correct 596 ms 125416 KB Output is correct
38 Correct 606 ms 125872 KB Output is correct
39 Correct 539 ms 125904 KB Output is correct
40 Correct 582 ms 126368 KB Output is correct
41 Correct 558 ms 123044 KB Output is correct
42 Correct 638 ms 126432 KB Output is correct
43 Correct 517 ms 125216 KB Output is correct
44 Correct 663 ms 124088 KB Output is correct
45 Correct 600 ms 128356 KB Output is correct
46 Correct 567 ms 123592 KB Output is correct
47 Correct 597 ms 126036 KB Output is correct
48 Correct 614 ms 124176 KB Output is correct
49 Correct 619 ms 123468 KB Output is correct
50 Correct 731 ms 125060 KB Output is correct
51 Correct 674 ms 123740 KB Output is correct
52 Correct 692 ms 124048 KB Output is correct
53 Correct 589 ms 124264 KB Output is correct
54 Correct 659 ms 124088 KB Output is correct
55 Correct 640 ms 123700 KB Output is correct
56 Correct 601 ms 123372 KB Output is correct
57 Correct 659 ms 124492 KB Output is correct
58 Correct 646 ms 124048 KB Output is correct
59 Correct 645 ms 125112 KB Output is correct
60 Correct 636 ms 116648 KB Output is correct
61 Correct 660 ms 125200 KB Output is correct
62 Correct 607 ms 124952 KB Output is correct
63 Incorrect 523 ms 116916 KB Output isn't correct
64 Halted 0 ms 0 KB -