HDU 4866

Shooting

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 433 Accepted Submission(s): 62

Problem Description

In the shooting game, the player can choose to stand in the position of [1, X] to shoot, you can shoot all the nearest K targets. The value of K may be different on different shootings. There are N targets to shoot, each target occupy the position of [Li, Ri] , the distance from the starting line is Di(1<=i<=N). Shooting a target can get the bonus points equal to the distance to the starting line. After each shooting targets still exist. Additional, if the previous bonus points is more than P, then as a reward for the shooting present bonus points doubled(and then check the next one). Player wants to know the bonus points he got in each shot.

Input

The input consists several test cases. The first line has two integers, N, M, X, P(1<=N, M ,X<=100000, P<=1000000000), N represents the total number of target shooting, M represents the number of shooting. The next N lines of three integers L, R, D (1<=L<=R<=X, 1<=D<=10000000), occupy the position of [L, R] and the distance from the starting line is D. The next M lines, each line contains four integers x, a, b, c (1<=x<=X, 0<=a,b<=N, 1<=c<=10000000), and K = ( a * Pre + b ) % c. Pre is the bonus point of previous shooting , and for the first shooting Pre=1. It denotes standing in the position x and the player can shoot the nearest K targets.

Output

Output M lines each corresponds to one integer.

Sample Input

4 3 5 8 1 2 6 2 3 3 2 4 7 1 5 2 2 2 1 5 3 1 1 10 4 2 3 7

Sample Output

11 10 18

Author

FZU

Source

2014 Multi-University Training Contest 1

y坐标离散化一下。 线段树维护。 加入主席树。 按照从左到右加入，左端点加，右端点减。   线段树一个是记录个数，一个是记录和。

/* ***
Author :kuangbin
Created Time :2014/7/23 23:37:24
File Name :E:\2014ACM\比赛\2014多校训练\2014多校1\HDU4866.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 200010;
const int M = MAXN * 100;
int n,tot;
int T[MAXN];
int lson[M],rson[M];
int c1[M];
long long c2[M];
int build(int l,int r)
{
int root = tot++;
c1[root] = 0; c2[root] = 0;
if(l != r)
{
int mid = (l+r)/2;
lson[root] = build(l,mid);
rson[root] = build(mid+1,r);
}
return root;
}
int update(int root,int pos,int val1,long long val2)
{
int newroot = tot++, tmp = newroot;
c1[newroot] = c1[root] + val1;
c2[newroot] = c2[root] + val2;
int l = 1, r = n;
while(l < r)
{
int mid = (l+r)/2;
if(pos <= mid)
{
lson[newroot] = tot++; rson[newroot] = rson[root];
newroot = lson[newroot]; root = lson[root];
r = mid;
}
else
{
rson[newroot] = tot++; lson[newroot] = lson[root];
newroot = rson[newroot]; root = rson[root];
l = mid+1;
}
c1[newroot] = c1[root] + val1;
c2[newroot] = c2[root] + val2;
}
return tmp;
}
long long query(int root,int K)
{
long long ret = 0;
int l = 1, r = n;
while(l < r)
{
int mid = (l+r)/2;
if(c1[lson[root]] >= K)
{
r = mid;
root = lson[root];
}
else
{
K -= c1[lson[root]];
ret += c2[lson[root]];
root = rson[root];
l = mid+1;
}
}
return ret + c2[root];
}

struct Node
{
int x;
int D;
int index;
Node(int _x = 0,int _D = 0,int _index = 0)
{
x = _x;
D = _D;
index = _index;
}
}node[MAXN];
bool cmp(Node a,Node b)
{
if(a.x != b.x)return a.x < b.x;
else return a.D > b.D;
}
int y[MAXN];
int ind[MAXN];
bool cmp2(int a,int b)
{
return y[a] < y[b];
}
int rind[MAXN];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int N,MM,X,P;
while(scanf(“%d%d%d%d”,&N,&MM,&X,&P) == 4)
{
tot = 0;
int cnt = 0;
int cnty = 0;
int L,R,D;
for(int i = 0;i < N;i++)
{
scanf(“%d%d%d”,&L,&R,&D);
y[cnty++] = D;
ind[i] = i;
node[++cnt] = Node(L,D,i);
node[++cnt] = Node(R,-D,i);
}
sort(ind,ind+N,cmp2);
for(int i = 0;i < N;i++)
rind[ind[i]] = i+1;
n = N;
sort(node+1,node+cnt+1,cmp);
T[0] = build(1,n);
for(int i = 1;i <= cnt;i++)
{
if(node[i].D > 0)
T[i] = update(T[i-1],rind[node[i].index],1,node[i].D);
else
T[i] = update(T[i-1],rind[node[i].index],-1,node[i].D);
}
int x,a,b,c;
long long pre = 1;
while(MM–)
{
scanf(“%d%d%d%d”,&x,&a,&b,&c);
int id = 0;
int l = 1, r = cnt;
while(l <= r)
{
int mid = (l+r)/2;
if(node[mid].x < x || (node[mid].x == x && node[mid].D > 0))
{
id = mid;
l = mid+1;
}
else
{
r = mid-1;
}
}
int K = (pre%ca%c+b)%c;
if(K == 0)
{
printf(“0\n”);
pre = 0;
continue;
}
long long ans = query(T[id],K);
if(pre > P)ans = 2;
printf(“%I64d\n”,ans);
pre = ans;
}
}
return 0;
}