oj.uz

Submission #262166

# Submission time Handle Problem Language Result Execution time Memory
262166 2020-08-12T12:41:20 Z sckmd Examination (JOI19_examination) C++14
43 / 100
 2389 ms 1048580 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[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]] && 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 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 53 ms 31096 KB Output is correct
8 Correct 53 ms 31096 KB Output is correct
9 Correct 55 ms 31096 KB Output is correct
10 Correct 51 ms 30840 KB Output is correct
11 Correct 46 ms 26232 KB Output is correct
12 Correct 18 ms 7544 KB Output is correct
13 Correct 52 ms 31096 KB Output is correct
14 Correct 63 ms 31224 KB Output is correct
15 Correct 54 ms 31228 KB Output is correct
16 Correct 45 ms 26232 KB Output is correct
17 Correct 52 ms 30840 KB Output is correct
18 Correct 13 ms 6784 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2164 ms 636004 KB Output is correct
2 Correct 2076 ms 636016 KB Output is correct
3 Correct 2076 ms 636372 KB Output is correct
4 Correct 1648 ms 630148 KB Output is correct
5 Correct 1018 ms 300020 KB Output is correct
6 Correct 780 ms 236424 KB Output is correct
7 Correct 2137 ms 636228 KB Output is correct
8 Correct 2085 ms 636356 KB Output is correct
9 Correct 2021 ms 636152 KB Output is correct
10 Correct 747 ms 290560 KB Output is correct
11 Correct 1576 ms 629916 KB Output is correct
12 Correct 457 ms 213620 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2164 ms 636004 KB Output is correct
2 Correct 2076 ms 636016 KB Output is correct
3 Correct 2076 ms 636372 KB Output is correct
4 Correct 1648 ms 630148 KB Output is correct
5 Correct 1018 ms 300020 KB Output is correct
6 Correct 780 ms 236424 KB Output is correct
7 Correct 2137 ms 636228 KB Output is correct
8 Correct 2085 ms 636356 KB Output is correct
9 Correct 2021 ms 636152 KB Output is correct
10 Correct 747 ms 290560 KB Output is correct
11 Correct 1576 ms 629916 KB Output is correct
12 Correct 457 ms 213620 KB Output is correct
13 Correct 2297 ms 636304 KB Output is correct
14 Correct 2185 ms 636280 KB Output is correct
15 Correct 2061 ms 636160 KB Output is correct
16 Correct 1823 ms 630264 KB Output is correct
17 Correct 1041 ms 300160 KB Output is correct
18 Correct 717 ms 236532 KB Output is correct
19 Correct 2300 ms 636356 KB Output is correct
20 Correct 2247 ms 636464 KB Output is correct
21 Correct 2385 ms 636560 KB Output is correct
22 Correct 755 ms 290544 KB Output is correct
23 Correct 1556 ms 629768 KB Output is correct
24 Correct 459 ms 213800 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 53 ms 31096 KB Output is correct
8 Correct 53 ms 31096 KB Output is correct
9 Correct 55 ms 31096 KB Output is correct
10 Correct 51 ms 30840 KB Output is correct
11 Correct 46 ms 26232 KB Output is correct
12 Correct 18 ms 7544 KB Output is correct
13 Correct 52 ms 31096 KB Output is correct
14 Correct 63 ms 31224 KB Output is correct
15 Correct 54 ms 31228 KB Output is correct
16 Correct 45 ms 26232 KB Output is correct
17 Correct 52 ms 30840 KB Output is correct
18 Correct 13 ms 6784 KB Output is correct
19 Correct 2164 ms 636004 KB Output is correct
20 Correct 2076 ms 636016 KB Output is correct
21 Correct 2076 ms 636372 KB Output is correct
22 Correct 1648 ms 630148 KB Output is correct
23 Correct 1018 ms 300020 KB Output is correct
24 Correct 780 ms 236424 KB Output is correct
25 Correct 2137 ms 636228 KB Output is correct
26 Correct 2085 ms 636356 KB Output is correct
27 Correct 2021 ms 636152 KB Output is correct
28 Correct 747 ms 290560 KB Output is correct
29 Correct 1576 ms 629916 KB Output is correct
30 Correct 457 ms 213620 KB Output is correct
31 Correct 2297 ms 636304 KB Output is correct
32 Correct 2185 ms 636280 KB Output is correct
33 Correct 2061 ms 636160 KB Output is correct
34 Correct 1823 ms 630264 KB Output is correct
35 Correct 1041 ms 300160 KB Output is correct
36 Correct 717 ms 236532 KB Output is correct
37 Correct 2300 ms 636356 KB Output is correct
38 Correct 2247 ms 636464 KB Output is correct
39 Correct 2385 ms 636560 KB Output is correct
40 Correct 755 ms 290544 KB Output is correct
41 Correct 1556 ms 629768 KB Output is correct
42 Correct 459 ms 213800 KB Output is correct
43 Runtime error 2389 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Halted 0 ms 0 KB -