Cod sursa(job #1867207)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 3 februarie 2017 20:52:04
Problema Peste Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.77 kb
#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;
}