Submission #262212

#	Time	Username	Problem	Language	Result	Execution time	Memory
262212		sckmd	Examination (JOI19_examination)	C++14	0 / 100	805 ms	7788 KiB

examination

#include <bits/stdc++.h>

using namespace std;
#define MAXN 100005
int a[MAXN];
int b[MAXN];
int sol[MAXN];
int n;
int BLOCK;
vector <int> ids;
vector <int> idsz;

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 a[x]>a[y];
}
bool cmppp(int x,int y)
{
  return b[x]<b[y];
}
vector <int> strk[400];
int pozniz[MAXN];
bool active[MAXN];

void update(int origid)
{
  int pozuniz = pozniz[origid];
  int bl = pozuniz/BLOCK;
  strk[bl].push_back(a[origid]+b[origid]);
  sort(strk[bl].begin(),strk[bl].end());
  active[origid]=true;
}

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

int query(int y,int z)
{
  int ans = 0;
  int bl = 0;
  int startpos = lowb(y);
  while(startpos%BLOCK != 0 && startpos < n)
  {
    if(!active[idsz[startpos]]){startpos++;continue;}
    if(a[idsz[startpos]]+b[idsz[startpos]] >= z)ans++;
    startpos++;
  }
  if(startpos % BLOCK != 0 || startpos == n)return ans;
  for(int bl = startpos/BLOCK; bl <= (n-1)/BLOCK; bl++)
  {
    auto it = lower_bound(strk[bl].begin(),strk[bl].end(),z);
    int pos = it-strk[bl].begin();
    ans += max(0,n-1-pos+1);
  }
  return ans;
}

int main()
{
  ios_base::sync_with_stdio(false);
  int q;
  cin >> n >> q;
  BLOCK = sqrt(n);
  for(int i = 0; i < n; i++)
  {
    cin >> a[i] >> b[i];
    ids.push_back(i);
    idsz.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);
  sort(idsz.begin(),idsz.end(),cmppp);
  for(int i = 0; i < idsz.size(); i++)pozniz[idsz[i]]=i;
  int now = 0;
  for(int i = 0; i < q; i++)
  {
    while(qq[i].x <= a[ids[now]] && now < n)update(now),now++;
    sol[qq[i].id]=query(qq[i].y,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 (stderr)

examination.cpp: In function 'int lowb(int)':
examination.cpp:52:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     mid=lo+hi>>1;
      |         ~~^~~
examination.cpp: In function 'int query(int, int)':
examination.cpp:62:7: warning: unused variable 'bl' [-Wunused-variable]
   62 |   int bl = 0;
      |       ^~
examination.cpp: In function 'int main()':
examination.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for(int i = 0; i < idsz.size(); i++)pozniz[idsz[i]]=i;
      |                  ~~^~~~~~~~~~~~~

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