Submission #813362

#	Time	Username	Problem	Language	Result	Execution time	Memory
813362		1075508020060209tc	Fire (JOI20_ho_t5)	C++14	100 / 100	743 ms	133772 KiB

ho_t5

#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 (stderr)

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 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80