제출 #1270154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270154		k12_khoi	Examination (JOI19_examination)	C++17	22 / 100	3095 ms	4548 KiB

examination

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int N=1e5+5;

struct queries
{
    int X,Y,Z,ID;
} Q[N];

bool cmp_X(queries x,queries y)
{
    return x.X<y.X;
}


int n,request,l,r,h;
int ans[N],bit[N];
pii a[N];
bool ok;
vector <int> ve;


namespace sub1
{
    int x,y,z,res;

    void solve()
    {
        for (int j=1;j<=request;j++)
        {
            x=Q[j].X;
            y=Q[j].Y;
            z=Q[j].Z;

            res=0;

            for (int i=1;i<=n;i++)
            if (a[i].X>=x and a[i].Y>=y and a[i].X+a[i].Y>=z) res++;

            cout << res << '\n';
        }
    }
}

namespace sub2
{
    void update(int u,int v)
    {
        for (int idx=u;idx<=h;idx+=idx&-idx)
        bit[idx]+=v;
    }

    int get(int u)
    {
        int ans=0;

        for (int idx=u;idx>0;idx-=idx&-idx)
        ans+=bit[idx];

        return ans;
    }

    void solve()
    {
        cin >> n >> request;

        ve.clear();
        for (int i=1;i<=n;i++)
        ve.push_back(a[i].Y);

        sort(ve.begin(),ve.end());
        ve.resize(unique(ve.begin(),ve.end())-ve.begin());
        h=ve.size();

        for (int i=1;i<=n;i++)
        a[i].Y=lower_bound(ve.begin(),ve.end(),a[i].Y)-ve.begin()+1;

        sort(a+1,a+n+1);


        sort(Q+1,Q+request+1,cmp_X);


        for (int i=1;i<=h;i++)
        bit[i]=0;

        l=n;
        for (int i=request;i>=1;i--)
        {
            while (l>=1 and a[l].X>=Q[i].X)
            {
                update(a[l].Y,1);
                l--;
            }

            ans[Q[i].ID]=get(h)-get(lower_bound(ve.begin(),ve.end(),Q[i].Y)-ve.begin());
        }

        for (int i=1;i<=request;i++)
        cout << ans[i] << '\n';
    }
}


int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> request;

    for (int i=1;i<=n;i++)
    cin >> a[i].X >> a[i].Y;

    ok=true;
    for (int i=1;i<=request;i++)
    {
        cin >> Q[i].X >> Q[i].Y >> Q[i].Z;
        Q[i].ID=i;

        if (Q[i].Z!=0) ok=false;
    }

    if (ok) sub2::solve();
    else sub1::solve();
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57