oj.uz

Submission #262165

# Submission time Handle Problem Language Result Execution time Memory
262165 2020-08-12T12:40:32 Z sckmd Examination (JOI19_examination) C++14
2 / 100
 91 ms 31224 KB 
#include <bits/stdc++.h>

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

struct node
{
  node* nula;
  node* kec;
  int cnt = 0;
};
node* tree[2*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]] && now < n)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";
    sol[qq[i].id]=query(1,0,n-1,findlowb(qq[i].y),n-1,qq[i].z);
  }
  for(int i = 0; i < q; i++)cout << sol[i] << "\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

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 53 ms 31224 KB Output is correct
8 Correct 55 ms 31224 KB Output is correct
9 Correct 55 ms 31224 KB Output is correct
10 Correct 51 ms 30968 KB Output is correct
11 Correct 48 ms 26360 KB Output is correct
12 Correct 17 ms 7424 KB Output is correct
13 Correct 52 ms 31224 KB Output is correct
14 Correct 55 ms 31224 KB Output is correct
15 Correct 53 ms 31224 KB Output is correct
16 Correct 41 ms 26360 KB Output is correct
17 Correct 49 ms 30968 KB Output is correct
18 Correct 13 ms 6784 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 8308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 8308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 53 ms 31224 KB Output is correct
8 Correct 55 ms 31224 KB Output is correct
9 Correct 55 ms 31224 KB Output is correct
10 Correct 51 ms 30968 KB Output is correct
11 Correct 48 ms 26360 KB Output is correct
12 Correct 17 ms 7424 KB Output is correct
13 Correct 52 ms 31224 KB Output is correct
14 Correct 55 ms 31224 KB Output is correct
15 Correct 53 ms 31224 KB Output is correct
16 Correct 41 ms 26360 KB Output is correct
17 Correct 49 ms 30968 KB Output is correct
18 Correct 13 ms 6784 KB Output is correct
19 Runtime error 91 ms 8308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -