oj.uz

Submission #262164

# Submission time Handle Problem Language Result Execution time Memory
262164 2020-08-12T12:37:34 Z sckmd Examination (JOI19_examination) C++14
43 / 100
 2410 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 1 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 54 ms 31224 KB Output is correct
9 Correct 53 ms 31224 KB Output is correct
10 Correct 61 ms 30968 KB Output is correct
11 Correct 46 ms 26236 KB Output is correct
12 Correct 17 ms 7416 KB Output is correct
13 Correct 62 ms 31224 KB Output is correct
14 Correct 54 ms 31328 KB Output is correct
15 Correct 54 ms 31212 KB Output is correct
16 Correct 41 ms 26240 KB Output is correct
17 Correct 50 ms 30968 KB Output is correct
18 Correct 15 ms 6744 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2182 ms 638472 KB Output is correct
2 Correct 2106 ms 638172 KB Output is correct
3 Correct 2087 ms 638564 KB Output is correct
4 Correct 1677 ms 631300 KB Output is correct
5 Correct 1010 ms 301300 KB Output is correct
6 Correct 770 ms 237172 KB Output is correct
7 Correct 2103 ms 638196 KB Output is correct
8 Correct 2005 ms 638068 KB Output is correct
9 Correct 2025 ms 638068 KB Output is correct
10 Correct 817 ms 291696 KB Output is correct
11 Correct 1625 ms 631284 KB Output is correct
12 Correct 471 ms 214260 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2182 ms 638472 KB Output is correct
2 Correct 2106 ms 638172 KB Output is correct
3 Correct 2087 ms 638564 KB Output is correct
4 Correct 1677 ms 631300 KB Output is correct
5 Correct 1010 ms 301300 KB Output is correct
6 Correct 770 ms 237172 KB Output is correct
7 Correct 2103 ms 638196 KB Output is correct
8 Correct 2005 ms 638068 KB Output is correct
9 Correct 2025 ms 638068 KB Output is correct
10 Correct 817 ms 291696 KB Output is correct
11 Correct 1625 ms 631284 KB Output is correct
12 Correct 471 ms 214260 KB Output is correct
13 Correct 2381 ms 638524 KB Output is correct
14 Correct 2180 ms 638708 KB Output is correct
15 Correct 2098 ms 638148 KB Output is correct
16 Correct 1879 ms 631668 KB Output is correct
17 Correct 1045 ms 301748 KB Output is correct
18 Correct 721 ms 237044 KB Output is correct
19 Correct 2197 ms 638660 KB Output is correct
20 Correct 2201 ms 638652 KB Output is correct
21 Correct 2281 ms 638752 KB Output is correct
22 Correct 748 ms 291948 KB Output is correct
23 Correct 1635 ms 631120 KB Output is correct
24 Correct 476 ms 214388 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 1 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 54 ms 31224 KB Output is correct
9 Correct 53 ms 31224 KB Output is correct
10 Correct 61 ms 30968 KB Output is correct
11 Correct 46 ms 26236 KB Output is correct
12 Correct 17 ms 7416 KB Output is correct
13 Correct 62 ms 31224 KB Output is correct
14 Correct 54 ms 31328 KB Output is correct
15 Correct 54 ms 31212 KB Output is correct
16 Correct 41 ms 26240 KB Output is correct
17 Correct 50 ms 30968 KB Output is correct
18 Correct 15 ms 6744 KB Output is correct
19 Correct 2182 ms 638472 KB Output is correct
20 Correct 2106 ms 638172 KB Output is correct
21 Correct 2087 ms 638564 KB Output is correct
22 Correct 1677 ms 631300 KB Output is correct
23 Correct 1010 ms 301300 KB Output is correct
24 Correct 770 ms 237172 KB Output is correct
25 Correct 2103 ms 638196 KB Output is correct
26 Correct 2005 ms 638068 KB Output is correct
27 Correct 2025 ms 638068 KB Output is correct
28 Correct 817 ms 291696 KB Output is correct
29 Correct 1625 ms 631284 KB Output is correct
30 Correct 471 ms 214260 KB Output is correct
31 Correct 2381 ms 638524 KB Output is correct
32 Correct 2180 ms 638708 KB Output is correct
33 Correct 2098 ms 638148 KB Output is correct
34 Correct 1879 ms 631668 KB Output is correct
35 Correct 1045 ms 301748 KB Output is correct
36 Correct 721 ms 237044 KB Output is correct
37 Correct 2197 ms 638660 KB Output is correct
38 Correct 2201 ms 638652 KB Output is correct
39 Correct 2281 ms 638752 KB Output is correct
40 Correct 748 ms 291948 KB Output is correct
41 Correct 1635 ms 631120 KB Output is correct
42 Correct 476 ms 214388 KB Output is correct
43 Runtime error 2410 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Halted 0 ms 0 KB -