제출 #1271153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271153		quan606303	Examination (JOI19_examination)	C++17	22 / 100	3096 ms	34532 KiB

examination

#include <bits/stdc++.h>
bool M1;
#define int long long
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define memfull(a,b) memset(a,b,sizeof(a));
#define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout);
using namespace std;
const int MOD=1e9+7;
const int maxn=1e5+7;
struct node
{
    int X,Y,Z,id;
};
vector<node> a;
node buctranh[maxn];
node giamkhao[maxn];
int ans[maxn];
int n,q;
namespace sub1{
    bool check()
    {
        return (n<=3e3&&q<=3e3);
    }
    void solve()
    {
        for (int i=1;i<=q;i++)
        {
            int ans=0;
            for (int j=1;j<=n;j++)
            {
                if (giamkhao[i].X<=buctranh[j].X&&giamkhao[i].Y<=buctranh[j].Y&&giamkhao[i].Z<=buctranh[j].Z)ans++;
            }
            cout<<ans<<endl;
        }
    }
}
namespace sub2
{
    bool check()
    {
        for (int i=1;i<=q;i++)if (giamkhao[i].Z!=0||giamkhao[i].X>1e5||giamkhao[i].Y>1e5)return false;
        for (int i=1;i<=n;i++)if (buctranh[i].X>1e5||buctranh[i].Y>1e5)return false;
        return true;
    }
    bool cmp(node u,node v)
    {
        if (u.X!=v.X)return u.X>v.X;
        return u.id<v.id;
    }
    struct BIT
    {
        int N;
        vector<int> bit;
        BIT(int n):N(n),bit(n+5,0){}
        void upd(int x,int val)
        {
            for (;x<=N;x+=(x&-x))bit[x]+=val;
        }
        int get(int x)
        {
            int sum=0;
            for (;x>0;x&=(x-1))sum+=bit[x];
            return sum;
        }
        int get_range(int l,int r)
        {
            return get(r)-get(l-1);
        }
    };
    void solve()
    {
        sort(a.begin(),a.end(),cmp);
        BIT bit(maxn);
        for (auto i:a)
        {
            if (i.id==-1)bit.upd(i.Y+1,1);
           else ans[i.id] = bit.get_range(i.Y+1, maxn);

        }
        for (int i=1;i<=q;i++)cout<<ans[i]<<endl;
    }
}
namespace sub34
{
  struct ST
  {
    int N;
    vector<vector<int> > st;
    ST(int n):N(n),st(4*n+5,vector<int>(0)){}
    vector<int> Merge(const vector<int> &L,const vector<int> &R)
    {
        vector<int> vt;
        int i=0,j=0;
        while (i<(int)L.size()&&j<(int)R.size())
        {
            if (L[i]<=R[j])
            {
                vt.push_back(L[i]);
                i++;
            }
            else
            {
                vt.push_back(R[j]);
                j++;
            }
        }
        while (i<(int)L.size())
        {
            vt.push_back(L[i]);
            i++;
        }
        while (j<(int)R.size())
        {
            vt.push_back(R[j]);
            j++;
        }
        return vt;
    }
    int cal(const vector<int> &vt,int val)
    {
        return vt.size()-(lower_bound(vt.begin(),vt.end(),val)-vt.begin());
    }
    void upd(int id,int l,int r,int pos,int val)
    {
        if (l>pos||r<pos)return ;
        if (l==r)
        {
            st[id]=Merge(st[id],{val});
            return ;
        }
        int mid=(l+r)/2;
        upd(id*2,l,mid,pos,val);
        upd(id*2+1,mid+1,r,pos,val);
        st[id]=Merge(st[id*2],st[id*2+1]);
    }
    int get(int id,int l,int r,int u,int v,int val)
    {
        if (l>v||r<u)return 0;
        if (l>=u&&r<=v)return max(0LL,cal(st[id],val));
        int mid=(l+r)/2;
        return get(id*2,l,mid,u,v,val)+get(id*2+1,mid+1,r,u,v,val);
    }
  };
  bool cmp(node u,node v)
{
    if (u.X!=v.X)return u.X>v.X;
    return u.id<v.id;
}
  void solve()
  {
      vector<int> nen1,nen2,nen3;
      nen1.push_back(-1e18);
      nen2.push_back(-1e18);
      nen3.push_back(-1e18);
      for (auto i:a)
      {
          nen1.push_back(i.X);
          nen2.push_back(i.Y);
          nen3.push_back(i.Z);
      }
      sort(nen1.begin(),nen1.end());
      sort(nen2.begin(),nen2.end());
      sort(nen3.begin(),nen3.end());
      nen1.erase(unique(nen1.begin(),nen1.end()),nen1.end());
      nen2.erase(unique(nen2.begin(),nen2.end()),nen2.end());
      nen3.erase(unique(nen3.begin(),nen3.end()),nen3.end());
      for (auto &i:a)
      {
        i.X=lower_bound(nen1.begin(),nen1.end(),i.X)-nen1.begin();
        i.Y=lower_bound(nen2.begin(),nen2.end(),i.Y)-nen2.begin();
        i.Z=lower_bound(nen3.begin(),nen3.end(),i.Z)-nen3.begin();
      }
      sort(a.begin(),a.end(),cmp);
      int sz_X=(int)nen1.size();
      int sz_Y=(int)nen2.size();
      int sz_Z=(int)nen3.size();
      ST st(sz_Y);
      for (auto i:a)
      {
          if (i.id==-1)st.upd(1,1,sz_Y,i.Y,i.Z);
          else ans[i.id]=st.get(1,1,sz_Y,i.Y,sz_Y,i.Z);
      }
      for (int i=1;i<=q;i++)cout<<ans[i]<<endl;
  }
};
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for (int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        a.push_back({x,y,x+y,-1});
        buctranh[i]={x,y,x+y,-1};
    }
    for (int i=1;i<=q;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        a.push_back({x,y,z,i});
        giamkhao[i]={x,y,z,i};
    }
    if (sub1::check())sub1::solve();
    else if (sub2::check())sub2::solve();
    else sub34::solve();
    bool M2;
    cerr<<"-------------------------------------------------"<<endl;
    cerr<<"Time : "<<clock()<<" ms"<<endl;
    cerr<<"Memory : "<<abs(&M2-&M1)/1024/1024<<" MB"<<endl;
    cerr<<"-------------------------------------------------"<<endl;
    return 0;
}

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