Pagini recente » Cod sursa (job #2213474) | Cod sursa (job #2729439) | Cod sursa (job #1760020) | Cod sursa (job #2478175) | Cod sursa (job #1867207)
#include <cstdio>
#include <algorithm>
#include <cctype>
#define BUF_SIZE 1<<17
#define MAXN 500
#define LOGN 8
#define MAXM 200000
#define MAXT 1000000
struct mycreation{
int x, y, p;
bool operator < (const mycreation &u) const {
if(x!=u.x) return x<u.x;
else return y<u.y;
}
}v[MAXN+1];
int pos=BUF_SIZE;
char buf[BUF_SIZE];
FILE *fin;
std::vector <mycreation> q[MAXT+1];
int k, n, heap[MAXN+1], poz[MAXN+1], u[MAXN+1];
bool ap[MAXN+1];
int ans[MAXM+1];
inline char nextch(){
if(pos==BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos=0;
return buf[pos++];
}
inline int read(){
int x=0, s=1;
char ch=nextch();
while((!isdigit(ch))&&(ch!='-')) ch=nextch();
if(ch=='-') ch=nextch(), s=-1;
while(isdigit(ch)){
x=10*x+ch-'0';
ch=nextch();
}
return x*s;
}
inline int question(int x, int t){
int rez=0;
for(int pas=1<<LOGN; pas; pas>>=1)
if((rez+pas<=n)&&(v[rez+pas].x+1LL*v[rez+pas].y*t<=x))
rez+=pas;
return rez;
}
inline bool cmp(int p, int q){
mycreation a=v[u[p]], b=v[u[p]+1], c=v[u[q]], d=v[u[q]+1];
return 1LL*(b.x-a.x)*(c.y-d.y)<1LL*(d.x-c.x)*(a.y-b.y);
}
inline int tata(int p){
return p/2;
}
inline int fiust(int p){
return 2*p;
}
inline int fiudr(int p){
return 2*p+1;
}
inline void heapSwap(int p, int q){
int aux=heap[p];
heap[p]=heap[q];
heap[q]=aux;
poz[heap[p]]=p;
poz[heap[q]]=q;
}
inline void coborare(int p){
int q;
bool f=1;
while((f)&&(fiust(p)<=k)){
q=fiust(p);
if((fiudr(p)<=k)&&(cmp(heap[fiudr(p)], heap[q])))
p=fiudr(p);
if(cmp(heap[q], heap[p])){
heapSwap(p, q);
p=q;
}else f=0;
}
}
inline void urcare(int p){
if(p>k) return ;
while((p>1)&&(cmp(heap[p], heap[tata(p)]))){
heapSwap(p, tata(p));
p=tata(p);
}
}
inline void heapify(){
for(int i=tata(k); i>0; i--)
coborare(i);
}
inline void scoate(int p){
ap[p]=0;
heap[poz[p]]=heap[k];
poz[heap[k]]=poz[p];
k--;
int x=heap[poz[p]];
coborare(poz[x]);
urcare(poz[x]);
}
inline void baga(int p){
ap[p]=1;
heap[++k]=p;
poz[p]=k;
urcare(k);
}
inline void mySwap(int p){
if((u[p]-1>0)&&(ap[v[u[p]-1].p]))
scoate(v[u[p]-1].p);
if((u[p]+1<n)&&(ap[v[u[p]+1].p]))
scoate(v[u[p]+1].p);
scoate(p);
int q=v[u[p]+1].p;
mycreation aux=v[u[p]];
v[u[p]]=v[u[q]];
v[u[q]]=aux;
u[p]++;
u[q]--;
if((u[p]<n)&&(v[u[p]].y>v[u[p]+1].y))
baga(p);
if((u[q]-1>0)&&(v[u[q]-1].y>v[u[q]].y))
baga(v[u[q]-1].p);
}
int main(){
FILE *fout;
fin=fopen("kinetic.in", "r");
fout=fopen("kinetic.out", "w");
n=read();
int m=read();
for(int i=1; i<=n; i++){
v[i].x=read();
v[i].y=read();
}
std::sort(v+1, v+n+1);
for(int i=1; i<=n; i++){
u[i]=i;
v[i].p=i;
}
for(int i=1; i<n; i++)
if(v[i].y>v[i+1].y)
baga(i);
heapify();
for(int i=1; i<=m; i++){
int x=read();
int y=read();
int t=read();
mycreation a;
a.x=std::min(x, y);
a.y=std::max(x, y);
a.p=i;
q[t].push_back(a);
}
for(int i=0; i<=MAXT; i++){
while((k>0)&&(v[u[heap[1]]].x+1LL*i*v[u[heap[1]]].y>v[u[heap[1]]+1].x+1LL*i*v[u[heap[1]]+1].y))
mySwap(heap[1]);
for(auto x:q[i])
ans[x.p]=question(x.y, i)-question(x.x-1, i);
}
for(int i=1; i<=m; i++)
fprintf(fout, "%d\n", ans[i]);
fclose(fin);
fclose(fout);
return 0;
}