제출 #1334801

#제출 시각아이디문제언어결과실행 시간메모리
1334801a.pendovExamination (JOI19_examination)C++20
0 / 100
354 ms18704 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000009;
int A[MAXN],B[MAXN],C[MAXN],X[MAXN],Y[MAXN],Z[MAXN],ans[MAXN];
unordered_map<int,int> mp;
set<int> s;

struct Point
{
    int x,y;
};

vector<Point> points;

struct Query
{
    int x,y,indx,coef;
};

vector<Query> queries;

bool sorterP(Point& a,Point& b)
{
    return a.x<=b.x;
}

bool sorterQ(Query& a,Query& b)
{
    return a.x<=b.x;
}

int format(int N,int Q)
{
    for(auto i:queries)
    {
        s.insert(i.x);
        s.insert(i.y);
    }

    for(auto i:points)
    {
        s.insert(i.x);
        s.insert(i.y);
    }

    int curr=1;
    for(auto i:s)mp[i]=curr++;

    for(int i=0;i<N;i++)
    {
        points[i].x=mp[points[i].x];
        points[i].y=mp[points[i].y];
    }

    for(int i=0;i<Q;i++)
    {
        queries[i].x=mp[queries[i].x];
        queries[i].y=mp[queries[i].y];
    }

    sort(queries.begin(),queries.end(),sorterQ);
    sort(points.begin(),points.end(),sorterP);

    mp.clear();
    s.clear();
    return curr+100;
}

struct FENWICK
{
    int MAXSIZE;
    int fen[MAXN];

    int lp2(int a)
    {
        return a&(-a);
    }

    void change(int a,int v)
    {
        while(a<MAXSIZE)
        {
            fen[a]+=v;
            a+=lp2(a);
        }
    }

    int query(int a)
    {
        int ans=0;
        while(a>0)
        {
            ans+=fen[a];
            a-=lp2(a);
        }

        return ans;
    }

    void clearAll()
    {
        for(int i=0;i<MAXSIZE;i++)fen[i]=0;
        MAXSIZE=0;
    }
};

FENWICK FEN;

void solve2D(int N,int Q)
{
    FEN.MAXSIZE=format(N,Q);

    int currP=0;

    for(auto q:queries)
    {
        while(currP<N&&points[currP].x<=q.x)
        {
            FEN.change(points[currP].y,1);
            currP++;
        }

        ans[q.indx]+=q.coef*FEN.query(q.y);
    }

    FEN.clearAll();
    queries.clear();
    points.clear();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N,Q;
    cin>>N>>Q;

    for(int i=0;i<N;i++)
    {
        cin>>A[i]>>B[i];
        C[i]=A[i]+B[i];
    }

    for(int i=0;i<Q;i++)
    {
        cin>>X[i]>>Y[i]>>Z[i];
    }


    for(int i=0;i<N;i++)
    {
        points.push_back({-A[i],-B[i]});
    }

    for(int i=0;i<Q;i++)
    {
        if(Z[i]<=X[i]+Y[i])
        {
            queries.push_back({-X[i],-Y[i],i,1});
        }
    }

    solve2D(N,queries.size());

    for(int i=0;i<N;i++)
    {
        points.push_back({A[i],-C[i]});
    }

    for(int i=0;i<Q;i++)
    {
        if(Z[i]>X[i]+Y[i])
        {
            queries.push_back({X[i]-1,-Z[i],i,-1});
        }
    }

    solve2D(N,queries.size());

    for(int i=0;i<N;i++)
    {
        points.push_back({B[i],-C[i]});
    }

    for(int i=0;i<Q;i++)
    {
        if(Z[i]>X[i]+Y[i])
        {
            queries.push_back({Y[i]-1,-Z[i],i,-1});
        }
    }

    solve2D(N,queries.size());

    for(int i=0;i<N;i++)
    {
        points.push_back({-C[i],0});
    }

    for(int i=0;i<Q;i++)
    {
        if(Z[i]>X[i]+Y[i])
        {
            queries.push_back({-Z[i],0,i,1});
        }
    }

    solve2D(N,queries.size());

    for(int i=0;i<Q;i++)
    {
        cout<<ans[i]<<'\n';
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...