oj.uz

Submission #749278

# Submission time Handle Problem Language Result Execution time Memory
749278 2023-05-27T16:25:30 Z 1075508020060209tc Fire (JOI20_ho_t5) C++14
6 / 100
 309 ms 43244 KB 
#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

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.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 7.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 42592 KB Output is correct
2 Correct 278 ms 42656 KB Output is correct
3 Correct 287 ms 43244 KB Output is correct
4 Correct 287 ms 42716 KB Output is correct
5 Correct 274 ms 42904 KB Output is correct
6 Correct 294 ms 42396 KB Output is correct
7 Correct 301 ms 42672 KB Output is correct
8 Correct 273 ms 42988 KB Output is correct
9 Correct 295 ms 42532 KB Output is correct
10 Correct 295 ms 42532 KB Output is correct
11 Correct 309 ms 42952 KB Output is correct
12 Correct 292 ms 42828 KB Output is correct
13 Correct 301 ms 42900 KB Output is correct
14 Correct 283 ms 43208 KB Output is correct

Subtask #5
0 / 80.0

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