/ Randle /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 6ms 8.309 MiB
#2 Accepted 5ms 6.305 MiB

代码

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<string>  
#include<algorithm>  
#include<cmath>  
using namespace std;   
  
int getint()  
{  
    int i=0,f=1;char c;  
    for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());  
    if(c=='-')f=-1,c=getchar();  
    for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';  
    return i*f;  
}  
  
const int N=1e5+5;  
int n,m,tot,cnt,b[N*6];  
long long bit[N*6],ans[N];  
struct point  
{  
    int x,y,val;  
    bool operator <(const point &a)const  
    {  
        return x==a.x?y<a.y:x<a.x;  
    }  
}a[N];  
struct question  
{  
    int x1,x2,y1,y2;  
}q[N];  
struct halfquestion  
{  
    int x,y1,y2,pos,k;  
    halfquestion(){}  
    halfquestion(int _x,int _y1,int _y2,int _pos,int _k):  
        x(_x),y1(_y1),y2(_y2),pos(_pos),k(_k){}  
    bool operator <(const halfquestion &a)const  
    {  
        return x<a.x;  
    }  
}g[N<<1];  
  
void lsh()  
{  
    sort(b+1,b+cnt+1);  
    cnt=unique(b+1,b+cnt+1)-b-1;  
    for(int i=1;i<=n;i++)  
    {  
        a[i].x=lower_bound(b+1,b+cnt+1,a[i].x)-b;  
        a[i].y=lower_bound(b+1,b+cnt+1,a[i].y)-b;  
    }  
    for(int i=1;i<=m;i++)  
    {  
        q[i].x1=lower_bound(b+1,b+cnt+1,q[i].x1)-b;  
        q[i].y1=lower_bound(b+1,b+cnt+1,q[i].y1)-b;  
        q[i].x2=lower_bound(b+1,b+cnt+1,q[i].x2)-b;  
        q[i].y2=lower_bound(b+1,b+cnt+1,q[i].y2)-b;  
    }  
}  
  
void update(int x,int val)  
{  
    for(int i=x;i<=cnt;i+=i&(-i))  
        bit[i]+=val;  
}  
  
long long query(int x)  
{  
    long long res=0;  
    for(int i=x;i>0;i-=i&(-i))  
        res+=bit[i];  
    return res;  
}  
  
int main()  
{  
    //freopen("lx.in","r",stdin);  
    n=getint(),m=getint();  
    for(int i=1;i<=n;i++)  
    {  
        b[++cnt]=a[i].x=getint();  
        b[++cnt]=a[i].y=getint();  
        a[i].val=getint();  
    }  
    for(int i=1;i<=m;i++)  
    {  
        b[++cnt]=q[i].x1=getint(),b[++cnt]=q[i].y1=getint();  
        b[++cnt]=q[i].x2=getint(),b[++cnt]=q[i].y2=getint();  
    }  
    lsh();  
    for(int i=1;i<=m;i++)  
    {  
        g[++tot]=halfquestion(q[i].x1-1,q[i].y1,q[i].y2,i,-1);  
        g[++tot]=halfquestion(q[i].x2,q[i].y1,q[i].y2,i,1);  
    }  
    sort(a+1,a+n+1);  
    sort(g+1,g+tot+1);  
    for(int i=1,j=1;i<=tot;i++)  
    {  
        while(j<=n&&a[j].x<=g[i].x)  
            update(a[j].y,a[j].val),j++;  
        ans[g[i].pos]+=(query(g[i].y2)-query(g[i].y1-1))*g[i].k;  
    }  
    for(int i=1;i<=m;i++)  
        printf("%lld\n",ans[i]);  
    return 0;  
}  

信息

递交者
类型
递交
题目
老C的任务
题目数据
下载
语言
C++
递交时间
2017-10-01 16:20:06
评测时间
2017-10-01 16:20:06
评测机
分数
100
总耗时
11ms
峰值内存
8.309 MiB