답안 #262208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
262208	2020-08-12T13:29:36 Z	sckmd	Examination (JOI19_examination)	C++14	컴파일 오류	0 ms	0 KB

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;
};

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(q[i].x <= a[ids[now]] && now < n)update(now),now++;
    ans[q[i].id]=query(q[i].y,q[i].z);
  }
  for(int i = 0; i < q; i++)cout << ans[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 lowb(int)':
examination.cpp:50:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     mid=lo+hi>>1;
      |         ~~^~~
examination.cpp: In function 'int query(int, int)':
examination.cpp:60:7: warning: unused variable 'bl' [-Wunused-variable]
   60 |   int bl = 0;
      |       ^~
examination.cpp: In function 'int main()':
examination.cpp:92:12: error: 'qq' was not declared in this scope; did you mean 'q'?
   92 |     cin >> qq[i].x >> qq[i].y >> qq[i].z;
      |            ^~
      |            q
examination.cpp:95:8: error: 'qq' was not declared in this scope; did you mean 'q'?
   95 |   sort(qq,qq+q,cmp);
      |        ^~
      |        q
examination.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for(int i = 0; i < idsz.size(); i++)pozniz[idsz[i]]=i;
      |                  ~~^~~~~~~~~~~~~
examination.cpp:102:14: error: invalid types 'int[int]' for array subscript
  102 |     while(q[i].x <= a[ids[now]] && now < n)update(now),now++;
      |              ^
examination.cpp:103:5: error: 'ans' was not declared in this scope; did you mean 'abs'?
  103 |     ans[q[i].id]=query(q[i].y,q[i].z);
      |     ^~~
      |     abs
examination.cpp:103:12: error: invalid types 'int[int]' for array subscript
  103 |     ans[q[i].id]=query(q[i].y,q[i].z);
      |            ^
examination.cpp:103:27: error: invalid types 'int[int]' for array subscript
  103 |     ans[q[i].id]=query(q[i].y,q[i].z);
      |                           ^
examination.cpp:103:34: error: invalid types 'int[int]' for array subscript
  103 |     ans[q[i].id]=query(q[i].y,q[i].z);
      |                                  ^
examination.cpp:105:37: error: 'ans' was not declared in this scope; did you mean 'abs'?
  105 |   for(int i = 0; i < q; i++)cout << ans[i] << "\n";
      |                                     ^~~
      |                                     abs