Submission #749278

#	Time	Username	Problem	Language	Result	Execution time	Memory
749278		1075508020060209tc	Fire (JOI20_ho_t5)	C++14	6 / 100	309 ms	43244 KiB

ho_t5

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int lowbit(int x){return x&-x;}
int bit[500005];

void upd(int pl,int x){
while(pl<=500000){
    bit[pl]+=x;
    pl+=lowbit(pl);
}
}
int qsum(int pl){
int ret=0;
while(pl){
    ret+=bit[pl];
    pl-=lowbit(pl);
}
return ret;
}

int n;int Q;
int ar[500005];
vector<int>op[500005];
vector<int>qry[500005];
int ql[500005];int qr[500005];
int ans[500005];



signed main(){
cin>>n>>Q;
for(int i=1;i<=n;i++){
    cin>>ar[i];
}
for(int i=1;i<=Q;i++){
    int t;
    cin>>t>>ql[i]>>qr[i];
    qry[t].push_back(i);
}
int lst=-1;
for(int i=1;i<=n;i++){
    if(ar[i]==2){
        lst=i;
    }
    if(lst>=1){
        op[i-lst].push_back(i);
    }
}
for(int i=0;i<=n+1;i++){
    for(int j=0;j<op[i].size();j++){
        upd(op[i][j],1);
    }
    for(int j=0;j<qry[i].size();j++){
        int id=qry[i][j];
        ans[id]=qr[id]-ql[id]+1+(qsum(qr[id])-qsum(ql[id]-1));
    }
}
for(int i=1;i<=Q;i++){
    cout<<ans[i]<<"\n";
}

}

Compilation message (stderr)

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

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