Submission #1274580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274580		quan606303	Examination (JOI19_examination)	C++17	100 / 100	505 ms	27280 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;
const int inf=1e18;
int n,q,ans[maxn];
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);
  }
};
struct point
{
  int X,Y,Z,id;
};
bool cmp1(point u,point v)
{
  if (u.X!=v.X)return u.X>v.X;
  return u.id<v.id;
}
bool cmp2(point u,point v)
{
  if (u.Y!=v.Y)return u.Y>v.Y;
  return u.id<v.id;
}
point a[2*maxn]; 
BIT bit(2*maxn);
void dnc(int l,int r)
{
  if (l>r)return ;
  int mid=(l+r)/2;
  vector<point> vt;
  for (int i=l;i<=r;i++)vt.push_back({i,a[i].Y,a[i].Z,a[i].id});
  sort(vt.begin(),vt.end(),cmp2);
  for (auto i:vt)
  {
    if (i.id==-1)
    {
      if (i.X<mid)
      {
        bit.upd(i.Z,1);
        if (a[mid].id!=-1&&i.Y>=a[mid].Y&&i.Z>=a[mid].Z)ans[a[mid].id]++;
      }
    }
    else 
    {
      if (i.X>mid)
      {
        ans[i.id]+=bit.get_range(i.Z,2*maxn-1);
        if (a[mid].id==-1&&a[mid].Y>=i.Y&&a[mid].Z>=i.Z)ans[i.id]++;
      }
    }
  }
  for (auto i:vt)
  {
    if (i.id==-1)
    {
      if (i.X<mid)bit.upd(i.Z,-1);
    }
  }
  dnc(l,mid-1);
  dnc(mid+1,r);
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    vector<int> nenX,nenY,nenZ;
    nenX.push_back(-inf);
    nenY.push_back(-inf);
    nenZ.push_back(-inf);
    for (int i=1;i<=n;i++)
    {
      int X,Y;
      cin>>X>>Y;
      int Z=X+Y;
      a[i]={X,Y,Z,-1};
      nenX.push_back(X);
      nenY.push_back(Y);
      nenZ.push_back(Z);
    }
    for (int i=1;i<=q;i++)
    {
      int X,Y,Z;
      cin>>X>>Y>>Z;
      a[n+i]={X,Y,Z,i};
      nenX.push_back(X);
      nenY.push_back(Y);
      nenZ.push_back(Z);
    }
    int N=n+q;
    sort(nenX.begin(),nenX.end());
    sort(nenY.begin(),nenY.end());
    sort(nenZ.begin(),nenZ.end());
    nenX.erase(unique(nenX.begin(),nenX.end()),nenX.end());
    nenY.erase(unique(nenY.begin(),nenY.end()),nenY.end());
    nenZ.erase(unique(nenZ.begin(),nenZ.end()),nenZ.end());
    for (int i=1;i<=N;i++)
    {
      a[i].X=lower_bound(nenX.begin(),nenX.end(),a[i].X)-nenX.begin();
      a[i].Y=lower_bound(nenY.begin(),nenY.end(),a[i].Y)-nenY.begin();
      a[i].Z=lower_bound(nenZ.begin(),nenZ.end(),a[i].Z)-nenZ.begin();
    }
    sort(a+1,a+1+N,cmp1);
  dnc(1,N);
  for (int i=1;i<=q;i++)cout<<ans[i]<<endl;
    return 0;
}

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