oj.uz

Submission #262160

# Submission time Handle Problem Language Result Execution time Memory
262160 2020-08-12T12:33:08 Z sckmd Examination (JOI19_examination) C++14
43 / 100
 2522 ms 1048580 KB 
#include <bits/stdc++.h>

using namespace std;
#define MAXN 200005
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 1 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 54 ms 31224 KB Output is correct
8 Correct 53 ms 31352 KB Output is correct
9 Correct 53 ms 31352 KB Output is correct
10 Correct 52 ms 30968 KB Output is correct
11 Correct 50 ms 26360 KB Output is correct
12 Correct 24 ms 7544 KB Output is correct
13 Correct 54 ms 31224 KB Output is correct
14 Correct 80 ms 31352 KB Output is correct
15 Correct 58 ms 31328 KB Output is correct
16 Correct 47 ms 26328 KB Output is correct
17 Correct 61 ms 30968 KB Output is correct
18 Correct 16 ms 6784 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2493 ms 635804 KB Output is correct
2 Correct 2260 ms 638096 KB Output is correct
3 Correct 2250 ms 638424 KB Output is correct
4 Correct 1789 ms 631520 KB Output is correct
5 Correct 1014 ms 301368 KB Output is correct
6 Correct 725 ms 237172 KB Output is correct
7 Correct 2143 ms 638496 KB Output is correct
8 Correct 2025 ms 638196 KB Output is correct
9 Correct 2098 ms 638128 KB Output is correct
10 Correct 824 ms 291716 KB Output is correct
11 Correct 1759 ms 631300 KB Output is correct
12 Correct 470 ms 214292 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2493 ms 635804 KB Output is correct
2 Correct 2260 ms 638096 KB Output is correct
3 Correct 2250 ms 638424 KB Output is correct
4 Correct 1789 ms 631520 KB Output is correct
5 Correct 1014 ms 301368 KB Output is correct
6 Correct 725 ms 237172 KB Output is correct
7 Correct 2143 ms 638496 KB Output is correct
8 Correct 2025 ms 638196 KB Output is correct
9 Correct 2098 ms 638128 KB Output is correct
10 Correct 824 ms 291716 KB Output is correct
11 Correct 1759 ms 631300 KB Output is correct
12 Correct 470 ms 214292 KB Output is correct
13 Correct 2351 ms 638604 KB Output is correct
14 Correct 2168 ms 638860 KB Output is correct
15 Correct 2077 ms 638452 KB Output is correct
16 Correct 1847 ms 631884 KB Output is correct
17 Correct 1040 ms 301908 KB Output is correct
18 Correct 778 ms 237036 KB Output is correct
19 Correct 2341 ms 638708 KB Output is correct
20 Correct 2220 ms 638848 KB Output is correct
21 Correct 2274 ms 638880 KB Output is correct
22 Correct 746 ms 291876 KB Output is correct
23 Correct 1623 ms 631440 KB Output is correct
24 Correct 467 ms 214256 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 1 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 54 ms 31224 KB Output is correct
8 Correct 53 ms 31352 KB Output is correct
9 Correct 53 ms 31352 KB Output is correct
10 Correct 52 ms 30968 KB Output is correct
11 Correct 50 ms 26360 KB Output is correct
12 Correct 24 ms 7544 KB Output is correct
13 Correct 54 ms 31224 KB Output is correct
14 Correct 80 ms 31352 KB Output is correct
15 Correct 58 ms 31328 KB Output is correct
16 Correct 47 ms 26328 KB Output is correct
17 Correct 61 ms 30968 KB Output is correct
18 Correct 16 ms 6784 KB Output is correct
19 Correct 2493 ms 635804 KB Output is correct
20 Correct 2260 ms 638096 KB Output is correct
21 Correct 2250 ms 638424 KB Output is correct
22 Correct 1789 ms 631520 KB Output is correct
23 Correct 1014 ms 301368 KB Output is correct
24 Correct 725 ms 237172 KB Output is correct
25 Correct 2143 ms 638496 KB Output is correct
26 Correct 2025 ms 638196 KB Output is correct
27 Correct 2098 ms 638128 KB Output is correct
28 Correct 824 ms 291716 KB Output is correct
29 Correct 1759 ms 631300 KB Output is correct
30 Correct 470 ms 214292 KB Output is correct
31 Correct 2351 ms 638604 KB Output is correct
32 Correct 2168 ms 638860 KB Output is correct
33 Correct 2077 ms 638452 KB Output is correct
34 Correct 1847 ms 631884 KB Output is correct
35 Correct 1040 ms 301908 KB Output is correct
36 Correct 778 ms 237036 KB Output is correct
37 Correct 2341 ms 638708 KB Output is correct
38 Correct 2220 ms 638848 KB Output is correct
39 Correct 2274 ms 638880 KB Output is correct
40 Correct 746 ms 291876 KB Output is correct
41 Correct 1623 ms 631440 KB Output is correct
42 Correct 467 ms 214256 KB Output is correct
43 Runtime error 2522 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Halted 0 ms 0 KB -