oj.uz

Submission #197276

# Submission time Handle Problem Language Result Execution time Memory
197276 2020-01-20T03:27:04 Z quocnguyen1012 Examination (JOI19_examination) C++14
41 / 100
 1148 ms 80804 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 25 ms 23800 KB Output is correct
4 Correct 25 ms 23800 KB Output is correct
5 Runtime error 58 ms 48128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 79844 KB Output is correct
2 Correct 789 ms 79712 KB Output is correct
3 Correct 823 ms 79816 KB Output is correct
4 Correct 436 ms 79204 KB Output is correct
5 Correct 642 ms 79348 KB Output is correct
6 Correct 355 ms 78552 KB Output is correct
7 Correct 751 ms 79840 KB Output is correct
8 Correct 732 ms 80804 KB Output is correct
9 Correct 817 ms 80784 KB Output is correct
10 Correct 551 ms 79188 KB Output is correct
11 Correct 425 ms 78920 KB Output is correct
12 Correct 339 ms 77344 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 79844 KB Output is correct
2 Correct 789 ms 79712 KB Output is correct
3 Correct 823 ms 79816 KB Output is correct
4 Correct 436 ms 79204 KB Output is correct
5 Correct 642 ms 79348 KB Output is correct
6 Correct 355 ms 78552 KB Output is correct
7 Correct 751 ms 79840 KB Output is correct
8 Correct 732 ms 80804 KB Output is correct
9 Correct 817 ms 80784 KB Output is correct
10 Correct 551 ms 79188 KB Output is correct
11 Correct 425 ms 78920 KB Output is correct
12 Correct 339 ms 77344 KB Output is correct
13 Correct 1148 ms 80160 KB Output is correct
14 Correct 1029 ms 79968 KB Output is correct
15 Correct 773 ms 79844 KB Output is correct
16 Correct 825 ms 79464 KB Output is correct
17 Correct 865 ms 79692 KB Output is correct
18 Correct 432 ms 78752 KB Output is correct
19 Correct 1106 ms 80092 KB Output is correct
20 Correct 1087 ms 80200 KB Output is correct
21 Correct 1029 ms 80072 KB Output is correct
22 Correct 560 ms 79300 KB Output is correct
23 Correct 422 ms 78824 KB Output is correct
24 Correct 336 ms 77408 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 25 ms 23800 KB Output is correct
4 Correct 25 ms 23800 KB Output is correct
5 Runtime error 58 ms 48128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -