Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
38756 baka24 【BJ】T3 C++ 通过 100 1677 MS 226344 KB 3400 2025-10-23 21:28:18

Tests(20/20):


#include<bits/stdc++.h> using namespace std; #define int long long #define lson (pos<<1) #define rson (pos<<1|1) #define ll long long #define pii pair<int,int> #define pil pair<int,ll> #define fr first #define sc second #define mk make_pair #define pb push_back #define LD long double ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} bool AAA; const int MAXN=500010,N=20;const LD eps=1e-7; int n,k,m; struct node{ int x,y,w; }s[MAXN]; struct point{ LD x; int y,w; bool operator<(const point&G)const{ return x<G.x; } }p[MAXN]; struct ques{ LD x; int l,r,id; bool operator<(const ques&G)const{ return x<G.x; } }; vector<ques>I[N],D[N]; pii a[N]; int as[MAXN]; const int inf=1e18; LD xl(int x,int y){return !x?y<0?-inf:inf:(LD)y/x;} bool cmp(pii x,pii y){return xl(x.fr,x.sc)<xl(y.fr,y.sc);} int d; int g[MAXN]; map<int,int>mp; struct treearray{ int C[MAXN]; int lb(int x){return x&(-x);} void upd(int x,int y){for(int i=x;i<=d;i+=lb(i))C[i]+=y;} int qry(int x){int res=0;for(int i=x;i>=1;i-=lb(i))res+=C[i];return res;} int qry(int l,int r){return qry(r)-qry(l-1);} }T; void slv(){ k=read(),n=read(),m=read(); for(int i=1;i<=k;i++)a[i].fr=read(),a[i].sc=read(); for(int i=1;i<=k;i++)if(a[i].fr<0)a[i].fr=-a[i].fr,a[i].sc=-a[i].sc; for(int i=1;i<=n;i++)s[i].x=read(),s[i].y=read(),s[i].w=read(); sort(a+1,a+k+1,cmp); for(int o=1;o<=m;o++){ int x=read(),y=read(),t=read(); for(int j=1;j<=k;j++)x-=t*a[j].fr,y-=t*a[j].sc; for(int j=1;j<=k;j++){ D[j].pb((ques){y-(LD)x*a[j].sc/a[j].fr,x+(j!=1),x+2*t*a[j].fr,o}); x+=2*t*a[j].fr,y+=2*t*a[j].sc; } for(int j=1;j<=k;j++){ I[j].pb((ques){y-(LD)x*a[j].sc/a[j].fr,x-2*t*a[j].fr,x-(j!=1),o}); x-=2*t*a[j].fr,y-=2*t*a[j].sc; } } for(int o=1;o<=k;o++){ sort(I[o].begin(),I[o].end()); sort(D[o].begin(),D[o].end()); d=0; for(int i=1;i<=n;i++)p[i].x=s[i].y-(LD)s[i].x*a[o].sc/a[o].fr,p[i].y=s[i].x,p[i].w=s[i].w,g[++d]=p[i].y; for(auto i:I[o])g[++d]=i.l,g[++d]=i.r; for(auto i:D[o])g[++d]=i.l,g[++d]=i.r; sort(g+1,g+d+1),d=unique(g+1,g+d+1)-g-1; for(int i=1;i<=n;i++)p[i].y=upper_bound(g+1,g+d+1,p[i].y)-g-1; for(int i=0;i<I[o].size();i++)I[o][i].l=upper_bound(g+1,g+d+1,I[o][i].l)-g-1,I[o][i].r=upper_bound(g+1,g+d+1,I[o][i].r)-g-1; for(int i=0;i<D[o].size();i++)D[o][i].l=upper_bound(g+1,g+d+1,D[o][i].l)-g-1,D[o][i].r=upper_bound(g+1,g+d+1,D[o][i].r)-g-1; sort(p+1,p+n+1); int it=1; for(int i=1;i<=d;i++)T.C[i]=0; for(auto i:I[o]){ while(it<=n&&i.x-p[it].x>-eps)T.upd(p[it].y,p[it].w),it++; as[i.id]+=T.qry(i.l,i.r); } for(int i=1;i<=d;i++)T.C[i]=0;it=1; for(auto i:D[o]){ while(it<=n&&i.x-p[it].x>eps)T.upd(p[it].y,p[it].w),it++; as[i.id]-=T.qry(i.l,i.r); } } for(int i=1;i<=m;i++)printf("%lld\n",as[i]); } signed main(){ //freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); //cerr<<(clock()*1.0)/CLOCKS_PER_SEC<<"s\n"; return 0; }


测评信息: