Submission #262158

#	Time	Username	Problem	Language	Result	Execution time	Memory
262158		sckmd	Examination (JOI19_examination)	C++14	0 / 100	2143 ms	635580 KiB

examination

#include <bits/stdc++.h>

using namespace std;
#define MAXN 200005
int a[MAXN];
int b[MAXN];
int n;

struct node
{
  node* nula;
  node* kec;
  int cnt = 0;
};
node* tree[4*MAXN];

void insert(int nod,int x)
{
  if(tree[nod] == NULL)tree[nod]=new node();
  node* now = tree[nod];
  now->cnt++;
  for(int i = 31; i >= 0; i--)
  {
    if(x&(1<<i))
    {
      if(now->kec == NULL)now->kec=new node();
      now=now->kec;
    }
    else
    {
      if(now->nula == NULL)now->nula=new node();
      now=now->nula;
    }
    now->cnt++;
  }
}
int querytrie(int nod,int x)
{
  //>=x?
  if(tree[nod]==NULL)return 0;
  node* now = tree[nod];
  int ans = 0;
  int i;
  for(i = 31; i >= 0; i--)
  {
    if(x&(1<<i))
    {
      if(now->kec==NULL)break;
      now=now->kec;
    }
    else
    {
      if(now->kec!=NULL)ans += now->kec->cnt;
      if(now->nula==NULL)break;
      now=now->nula;
    }
  }
  if(i==-1)ans+=now->cnt;
  return ans;
}
void update(int node,int left,int right,int idx,int val)
{
  insert(node,val);
  if(left==right)
  {
    return ;
  }
  int mid = left+right>>1;
  if(idx <= mid)update(node*2,left,mid,idx,val);
  else update(node*2+1,mid+1,right,idx,val);
}
int query(int node,int left,int right,int l,int r,int val)
{
  if(left > right || left > r || l > right)return 0;
  if(left >= l && right <= r)return querytrie(node,val);
  int mid = left+right>>1;
  return query(node*2,left,mid,l,r,val)+query(node*2+1,mid+1,right,l,r,val);
}

struct que
{
  int x,y,z;
  int id;
};
que qq[MAXN];

bool cmp(que a,que b)
{
  return a.x > b.x;
}
bool cmpp(int x,int y)
{
  return b[x] < b[y];
}
bool cmppp(int x,int y)
{
  return a[x]>a[y];
}

vector <int> ids;
vector <int> idsz;
int pozseg[MAXN];

int findlowb(int x)
{
  int lo = 0,hi=n-1,mid=lo+hi>>1,r=n;
  while(lo <= hi)
  {
    if(b[idsz[mid]] >= x)r=mid,hi=mid-1;
    else lo=mid+1;
    mid = lo+hi>>1;
  }
  return r;
}

int main()
{
  ios_base::sync_with_stdio(false);
  int q;
  cin >> n >> q;
  for(int i = 0; i < n; i++)
  {
    cin >> a[i] >> b[i];
    ids.push_back(i);
  }
  for(int i = 0; i < q; i++)
  {
    cin >> qq[i].x >> qq[i].y >> qq[i].z;
    qq[i].id=i;
  }
  sort(qq,qq+q,cmp);
  sort(ids.begin(),ids.end(),cmpp);
  idsz = ids;
  for(int i = 0; i < ids.size(); i++)
  {
    pozseg[ids[i]]=i;
  }
  sort(ids.begin(),ids.end(),cmppp);
  int now = 0;
  for(int i = 0; i < q; i++)
  {
    while(qq[i].x <= a[ids[now]])update(1,0,n-1,pozseg[ids[now]],a[ids[now]]+b[ids[now]]),now++;
    cout << query(1,0,n-1,findlowb(qq[i].y),n-1,qq[i].z) << "\n";
  }
  return 0;
}
/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
*/

Compilation message (stderr)

examination.cpp: In function 'void update(int, int, int, int, int)':
examination.cpp:68:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |   int mid = left+right>>1;
      |             ~~~~^~~~~~
examination.cpp: In function 'int query(int, int, int, int, int, int)':
examination.cpp:76:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |   int mid = left+right>>1;
      |             ~~~~^~~~~~
examination.cpp: In function 'int findlowb(int)':
examination.cpp:106:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |   int lo = 0,hi=n-1,mid=lo+hi>>1,r=n;
      |                         ~~^~~
examination.cpp:111:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |     mid = lo+hi>>1;
      |           ~~^~~
examination.cpp: In function 'int main()':
examination.cpp:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |   for(int i = 0; i < ids.size(); i++)
      |                  ~~^~~~~~~~~~~~

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