列表

详情

NC26006. Twinkle

描述

The Cartesian coordinate system is set in the sky. There you can see n stars, the i-th has coordinates (x_i, y_i), a maximum brightness c, equal for all stars, and an initial brightness .

Over time the stars twinkle. At moment 0 the i-th star has brightness s_i. Let at moment t a star has brightness x. Then at moment (t + 1) this star will have brightness x + 1, if , and 0 otherwise.
You want to look at the sky q times. In the i-th time you will look at the moment t_i and you will see a rectangle with sides parallel to the coordinate axes, the lower left corner has coordinates (x1_i, y1_i) and the upper right — (x2_i, y2_i). For each view, you want to know the total brightness of the stars lying in the viewed rectangle.

A star lies in a rectangle if it lies on its border or lies strictly inside it.

输入描述

The first line contains three integers n, q, c — the number of the stars, the number of the views and the maximum brightness of the stars.
The next n lines contain the stars description. The i-th from these lines contains three integers x_i, y_i, s_i— the coordinates of i-th star and its initial brightness.
The next q lines contain the views description. The i-th from these lines contains five integers t_i, x1_i, y1_i, x2_i, y2_i — the moment of the i-th view and the coordinates of the viewed rectangle.

For all coordinates,

输出描述

For each view print the total brightness of the viewed stars.

示例1

输入: 

3 3 5
1 1 2
2 3 0
3 3 1
0 1 1 3 3
1 2 2 3 3
2 2 1 3 3

输出: 

3
3
5

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 697ms, 内存消耗: 6320K, 提交时间: 2019-09-04 01:33:06 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+9;
int n,q,c,na,nx;
int f[N],x[N],tim[N];
void add(int x,int y){for(;x<N;x+=(x&-x))f[x]+=y;}
int query(int x){int ans=0;while(x)ans+=f[x],x-=(x&-x);return ans;}
ll ans[N],gs[N],les[N];
struct T{int x,y,s,z,id;}a[N];
bool cmp1(T t1,T t2){if(t1.x!=t2.x)return t1.x<t2.x;return t1.id<t2.id;}/***很重要的一步 插入优先于查询***/
bool cmp2(T t1,T t2){if(t1.y!=t2.y)return t1.y<t2.y;}
inline int getidx(int y){return lower_bound(x+1,x+nx+1,y)-x;}
void cdq(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq(l,mid),cdq(mid+1,r);
    sort(a+l,a+mid+1,cmp2),sort(a+mid+1,a+r+1,cmp2);
    int p=l,js=0; ll he=0;
    for(int i=mid+1;i<=r;i++){
        while(p<=mid&&a[p].y<=a[i].y){if(a[p].id==0)add(a[p].s,1),js++,he+=x[a[p].s];p++;}
        if(a[i].id)gs[a[i].id]+=js*a[i].z,ans[a[i].id]+=he*a[i].z,les[a[i].id]+=query(a[i].s)*a[i].z;
    }
    for(int i=l;i<p;i++)if(a[i].id==0)add(a[i].s,-1);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q>>c;
    for(int i=1,xx,y,s;i<=n;i++)cin>>xx>>y>>s,a[++na]=(T){xx,y,s,1,0},x[++nx]=s;
    for(int i=1,t,x1,y1,x2,y2;i<=q;i++){
        cin>>t>>x1>>y1>>x2>>y2;tim[i]=t;
        a[++na]=(T){x1-1,y1-1,c-t,1,i};
        a[++na]=(T){x1-1,y2,c-t,-1,i};
        a[++na]=(T){x2,y1-1,c-t,-1,i};
        a[++na]=(T){x2,y2,c-t,1,i};
        x[++nx]=c-t;
    }
    sort(x+1,x+nx+1);nx=unique(x+1,x+nx+1)-x-1;
    for(int i=1;i<=na;i++)a[i].s=getidx(a[i].s);
    sort(a+1,a+na+1,cmp1);
    cdq(1,na);
    for(int i=1;i<=q;i++)cout<<ans[i]+1ll*gs[i]*tim[i]-1ll*(gs[i]-les[i])*(c+1)<<endl;
    return 0;
}

上一题

© 2024 nowcoder.com