求调代码
  • 板块学术版
  • 楼主Zilljy258
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/4/12 17:32
  • 上次更新2023/10/23 18:41:24
查看原帖
求调代码
547725
Zilljy258楼主2023/4/12 17:32

错了一个挺大的数据。

求调,谢谢!


区间和

假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。

现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。

接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r] 之间的所有数的和。

输入格式 第一行包含两个整数 n 和 m。

接下来 n 行,每行包含两个整数 x 和 c。

再接下来 m 行,每行包含两个整数 l 和 r。

输出格式 共 m 行,每行输出一个询问中所求的区间内数字和。

数据范围 −109≤x≤109, 1≤n,m≤105, −109≤l≤r≤109, −10000≤c≤10000



输入样例:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5


我的代码:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m;
int top=0;
int use[400010];
int ci[400010];
struct pairr{
    int lw,rn;
}a[400010],c[400010];

int ef(int x){
    int l=1,r=top;
    while(l<r){
        int mid=l+r>>1;
        if(use[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].lw>>a[i].rn;
        use[++top]=a[i].lw;
    }
    for(int i=1;i<=m;i++){
        cin>>c[i].lw>>c[i].rn;
        use[++top]=c[i].lw;
        use[++top]=c[i].rn;
    }
    
    sort(use+1,use+top+1);
    unique(use+1,use+top+1);
    
    for(int i=1;i<=top;i++){
        if(use[i+1]<=use[i]){
            top=i;
            break;
        }
    }
    use[top+1]=0;
    for(int i=top+2;i<=400010;i++){
    	use[i]=use[i-1];
	}
    
    for(int i=1;i<=n;i++){
        ci[ef(a[i].lw)]=a[i].rn;
    }
    for(int i=1;i<=top;i++) ci[i]+=ci[i-1];
    
    for(int i=1;i<=m;i++){
        cout<<ci[ef(c[i].rn)]-ci[ef(c[i].lw)-1]<<endl;
    }
    
    return 0;
}

2023/4/12 17:32
加载中...