#include<stdio.h>
#include<algorithm>
#define BSIZ 300
int n,q;
int x[100100];
struct sn{
int loc,val;
bool operator<(const sn&r)const{
return val<r.val;
}
};
sn st[100100];
int a[100100];
int cpr[100100];
int qry[100100][2];
long long int ans[100100];
long long int sv[100100];
int cprn;
long long int it[1<<18];
void push(int loc,long long int val){
loc+=1<<17;
it[loc]=val;
loc/=2;
while(loc!=0){
if(it[loc*2]>it[loc*2+1]){
it[loc]=it[loc*2];
}
else{
it[loc]=it[loc*2+1];
}
if(it[loc]!=val)return;
loc/=2;
}
}
long long int calc(){
return it[1];
}
int main(){
int i,j,k,p,bf;
scanf("%d%d",&n,&q);
for(i=0;i<n;i++){
scanf("%d",&x[i]);
st[i].val=x[i];
st[i].loc=i;
}
std::sort(st,st+n);
for(i=0;i<n;i++){
a[st[i].loc]=cprn;
if(i==n-1||st[i].val!=st[i+1].val){
cpr[cprn]=st[i].val;
cprn++;
}
}
for(i=0;i<q;i++){
scanf("%d%d",&qry[i][0],&qry[i][1]);
qry[i][0]--;
qry[i][1]--;
st[i].loc=i;
st[i].val=qry[i][1];
}
std::sort(st,st+q);
for(i=0;i<=(n-1)/BSIZ;i++){
bf=i*BSIZ;
for(j=0;j<q;j++){
p=st[j].loc;
if(qry[p][0]/BSIZ==i){
for(k=bf;k<=qry[p][1];k++){
sv[a[k]]+=cpr[a[k]];
push(a[k],sv[a[k]]);
}
bf=qry[p][1]+1;
for(k=i*BSIZ;k<qry[p][0];k++){
sv[a[k]]-=cpr[a[k]];
push(a[k],sv[a[k]]);
}
ans[p]=calc();
for(k=i*BSIZ;k<qry[p][0];k++){
sv[a[k]]+=cpr[a[k]];
push(a[k],sv[a[k]]);
}
}
}
for(k=0;k<cprn;k++){
if(sv[k]==0)continue;
sv[k]=0;
push(k,0);
}
}
for(i=0;i<q;i++){
printf("%lld\n",ans[i]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
7436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
7436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
7436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
7436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
