Submission #262436

#	Time	Username	Problem	Language	Result	Execution time	Memory
262436		sckmd	Examination (JOI19_examination)	C++14	100 / 100	1849 ms	6252 KiB

examination

#include <bits/stdc++.h>

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

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> idsz;
vector <int> ids;
int pozicija[MAXN];
int BLOCK;
vector <int> moalgo[400];
bool active[MAXN];

void add(int idx)
{
  //idx orig niz
  int mopoz = pozicija[idx];
  int bl = mopoz/BLOCK;
  moalgo[bl].push_back(a[idx]+b[idx]);
  sort(moalgo[bl].begin(),moalgo[bl].end());
  active[idx]=true;
}

int query(int y,int z)
{
  int now = 0;
  while(1)
  {
    if(now >= n)break;
    int realid = ids[now];
    if(b[realid] >= y)break;
    now += BLOCK;
  }
  //cout << now << "\n";
  if(now >= n)
  {
  	int ret=0;
  	for(int j = n-1; j >= max(0,(n-1)-BLOCK); j--)
  	{
  		int realid = ids[j];
  		if(!active[realid])continue;
  		if(a[realid]+b[realid] >= z && b[realid]>=y)ret++;
  	}
  	return ret;
  }
  int ret = 0;
  int blo = now/BLOCK;
  if(blo > 0)
  {
    for(int j = max(0,now-BLOCK); j < now; j++)
    {
      int realid = ids[j];
      if(!active[realid])continue;
      if(a[realid]+b[realid]>=z && b[realid] >= y)ret++;
      //cout << j << " " << realid << "\n";
    }
  }
  //cout << "START BL " << blo << "\n";
  for(;now < n;blo += 1,now+=BLOCK)
  {
    auto it = lower_bound(moalgo[blo].begin(),moalgo[blo].end(),z);
    int pos = it-moalgo[blo].begin();
    ret += moalgo[blo].size()-pos;
    //cout << "BL " << blo << "\n";
  }
  return ret;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int q;
  cin >> n >> q;
  BLOCK = sqrt(n);
  for(int i = 0; i < n; i++)
  {
    cin >> a[i] >> b[i];
    idsz.push_back(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(idsz.begin(),idsz.end(),cmpp);
  sort(ids.begin(),ids.end(),cmppp);
  for(int i = 0; i < ids.size(); i++)pozicija[ids[i]]=i;
  int now = 0;
  for(int i = 0; i < q; i++)
  {
    while(now < n && a[idsz[now]] >= qq[i].x)add(idsz[now]),now++;//,cout << "ADDING " << idsz[now] << "\n";
    //cout << "QUERY " << qq[i].id << "\n";
    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 main()':
examination.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   for(int i = 0; i < ids.size(); i++)pozicija[ids[i]]=i;
      |                  ~~^~~~~~~~~~~~

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