Submission #813318

#	Time	Username	Problem	Language	Result	Execution time	Memory
813318		1075508020060209tc	Fire (JOI20_ho_t5)	C++14	0 / 100	585 ms	126692 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,i,ar[i]});
if(r&&l){
    event[r-i].push_back({r-1,i,-ar[i]});
    event[i-l].push_back({i-1,l,-ar[i]});
    event[r-i+i-l].push_back({r-1,l,ar[i]});
    return;
}
if(r){
    event[r-i].push_back({r-1,i,-ar[i]});
    return;
}
if(l){
    event[i-l].push_back({i-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() {
init();
mnf.init(1000000);
mns.init(1000000);
mnf2.init(1000000);
mns2.init(1000000);

for(int t=0;t<=10;t++){
       // cout<<t<<endl;
    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);
        mnf2.upd(a-1, (a-1)*c);
    }
    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);
        cal+=mns.qsum(p-t)+(mnf.qsum(1000000)-mnf.qsum(p-t))*(p-t);
        cal-=mns2.qsum(p)+(mnf2.qsum(1000000)-mnf2.qsum(p))*(p);
        if(qry[t][i].second<0){
            ans[id]-=cal;
        }else{
            ans[id]+=cal;
        }
    }
}
for(int i=1;i<=Q;i++){
    cout<<ans[i]<<endl;
}

}

Compilation message (stderr)

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

• Subtask 1: 0 / 1
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80