[ZOJ Monthly, January 2019]Little Sub and his Geometry Problem

Link

Solution

Q很小,每次询问可以O(n)。注意到,对于满足要求的(u,v),随着u的增大,v是单调递减的,就很好做了。
关键就是注意到这个单调性

Code

#include <bits/stdc++.h>

const int XN=1e5+11;

void Work() {
    static std::pair<int,int> p[XN];
    int w,n,q;
    std::cin>>w>>n;
    for(int i=1;i<=n;++i)
        std::cin>>p[i].first>>p[i].second;
    std::sort(p+1,p+1+n);
    std::cin>>q;
    while(q--) {
        long long c;std::cin>>c;
        int y=w,Ans=0;
        static int yc[XN];
        static long long ys[XN];
        for(int i=1;i<=w;++i)
            yc[i]=ys[i]=0;
        int cnt=0;long long sum=0;
        for(int x=1,i=1;x<=w;++x) {
            while(p[i].first==x) {
                if(p[i].second<=y) {
                    cnt++;sum+=p[i].first+p[i].second;
                    yc[p[i].second]++;ys[p[i].second]+=p[i].first+p[i].second;
                }
                i++;
            }
            while((long long)cnt*(x+y)-sum>c) {
                cnt-=yc[y];
                sum-=ys[y];
                y--;
            }
            if((long long)cnt*(x+y)-sum==c)
                Ans++;
        }
        std::cout<<Ans<<(q?' ':'\n');
    }
}

int main() {
//  freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注