oj.uz

Submission #262430

# Submission time Handle Problem Language Result Execution time Memory
262430 2020-08-12T22:38:37 Z sckmd Examination (JOI19_examination) C++14
0 / 100
 1063 ms 5704 KB 
#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;
  }
  if(now >= n)return 0;
  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++;
    }
  }
  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;
  }
  return ret;
}

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];
    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++;
    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

examination.cpp: In function 'int main()':
examination.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(int i = 0; i < ids.size(); i++)pozicija[ids[i]]=i;
      |                  ~~^~~~~~~~~~~~

Subtask #1
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 Incorrect 7 ms 640 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1063 ms 5704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1063 ms 5704 KB Output isn't correct
2 Halted 0 ms 0 KB -

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 Incorrect 7 ms 640 KB Output isn't correct
8 Halted 0 ms 0 KB -