Submission #197276

#	Time	Username	Problem	Language	Result	Execution time	Memory
197276		quocnguyen1012	Examination (JOI19_examination)	C++14	41 / 100	1148 ms	80804 KiB

examination

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 5e5 + 5;

class BIT2Dx {
  public:
  const int INF = 2e9;
  int n;
  vector<int> nodes[maxn];
  vector<int> f[maxn];

  void fakeUpdate(int u, int v){
    for (int x = u; x > 0; x -= x & -x)
      nodes[x].push_back(v);
  }

  void fakeGet(int u, int v){
    for (int x = u; x <= n; x += x & -x)
      nodes[x].push_back(v);
  }

  void update(int u, int v){
    for (int x = u; x > 0; x -= x & -x)
      for (int y = upper_bound(nodes[x].begin(), nodes[x].end(), v) - nodes[x].begin(); y > 0; y -= y & -y)
        f[x][y]++;
  }

  int get(int u, int v){
    int res = 0;
    for (int x = u; x <= n; x += x & -x)
      for (int y = lower_bound(nodes[x].begin(), nodes[x].end(), v) - nodes[x].begin() + 1; y <= nodes[x].size(); y += y & -y)
        res += f[x][y];
    return res;
  }
  void init(int _n){
      n = _n;
  }
  void normalize(void){
    for (int i = 1; i <= n; ++i){
      nodes[i].push_back(INF);
      sort(nodes[i].begin(), nodes[i].end());
      f[i].resize(nodes[i].size() + 3);
    }
  }
}ft;

int N, Q;
pair<int, int> stu[maxn];
int ans[maxn];
vector<int> val;

int compress(int x)
{
  return lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
}

class Query
{
  public:
  int A, B, C, id;
}query[maxn];

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> Q;
  ft.init(N * 3 + Q * 2);
  for (int i = 1; i <= N; ++i){
    cin >> stu[i].fi >> stu[i].se;
    val.pb(stu[i].fi); val.pb(stu[i].se); val.pb(stu[i].fi + stu[i].se);
  }
  for (int i = 1; i <= Q; ++i){
    query[i].id = i;
    cin >> query[i].A >> query[i].B >> query[i].C;
    val.pb(query[i].A); val.pb(query[i].B); val.pb(query[i].C);
  }
  sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end());
  sort(stu + 1, stu + 1 + N, greater<pair<int, int>>());
  sort(query + 1, query + 1 + N, [&](const Query & x, const Query & y){
    return x.A > y.A;
  });
  int j = 1;
  for (int i = 1; i <= Q; ++i){
    while (j <= N && stu[j].fi >= query[i].A){
      ft.fakeUpdate(compress(stu[j].se), compress(stu[j].fi + stu[j].se));
      ++j;
    }
    ft.fakeGet(compress(query[i].B), compress(query[i].C));
  }
  ft.normalize();
  j = 1;
  for (int i = 1; i <= Q; ++i){
    while (j <= N && stu[j].fi >= query[i].A){
      ft.update(compress(stu[j].se), compress(stu[j].fi + stu[j].se));
      ++j;
    }
    ans[query[i].id] = ft.get(compress(query[i].B), compress(query[i].C));
    //cerr << ft.get(compress(query[i].B), compress(query[i].C));
  }
  for (int i = 1; i <= Q; ++i){
    cout << ans[i] << '\n';
  }
}

Compilation message (stderr)

examination.cpp: In member function 'int BIT2Dx::get(int, int)':
examination.cpp:39:95: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int y = lower_bound(nodes[x].begin(), nodes[x].end(), v) - nodes[x].begin() + 1; y <= nodes[x].size(); y += y & -y)
                                                                                             ~~^~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:75:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
examination.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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