Submission #102225

#	Time	Username	Problem	Language	Result	Execution time	Memory
102225		ruhanhabib39	Examination (JOI19_examination)	C++17	100 / 100	1233 ms	106720 KiB

examination

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5;

struct Score {
   int s, t;
   int sum() const {
      return s + t;
   }
   bool operator<(Score o) const {
      if(sum() != o.sum()) return sum() > o.sum();
      if(s != o.s) return s < o.s;
      return t < o.t;
   }
};

struct Query {
   int i, a, b, c;
   bool operator<(Query q) const {
      if(c != q.c) return c > q.c;
      return i < q.i;
   }
};

int N, Q;
Score scores[MAXN + 10];
Query queries[MAXN + 10];
int res[MAXN + 10];

vector<int> svals, tvals;

void compress() {
   for(int i = 0; i < N; i++) {
      svals.push_back(scores[i].s);
      tvals.push_back(scores[i].t);
   }

   sort(svals.begin(), svals.end());
   svals.erase(unique(svals.begin(), svals.end()), svals.end());

   sort(tvals.begin(), tvals.end());
   tvals.erase(unique(tvals.begin(), tvals.end()), tvals.end());
}

struct SegT {
   int L, R, cc;
};

int tree[MAXN + 10];
SegT tree_t[int(1e7) + 10];

int create_seg_t(int l, int r, int cc) {
   static int ii = 0;
   tree_t[ii].L = l;
   tree_t[ii].R = r;
   tree_t[ii].cc = cc;
   ++ii;
   return ii - 1;
}

int get_t(int cn, int b, int e, int l, int r) {
   if(r < b || l > e || cn == -1) return 0;
   if(l <= b && e <= r) return tree_t[cn].cc;
   int m = (b + e) / 2;
   return get_t(tree_t[cn].L, b, m, l, r) + get_t(tree_t[cn].R, m+1, e, l, r);
}

int get_t(int cn, int ti) {
   return get_t(cn, 0, tvals.size() - 1, ti, tvals.size() - 1);
}

int get(int si, int ti) {
   si = svals.size() - si; // 0 -> n, n - 1 -> 1
   int rs = 0;
   while(si > 0) {
      rs += get_t(tree[si], ti);
      si -= si & (-si);
   }
   return rs;
}

int upd_t(int cn, int b, int e, int i) {
   //cerr << "upd_t(" << cn << ", [" << b << ", " << e << "], " << i << ")\n";
   //cerr << "-------->\n\n";
   if(cn == -1) {
      cn = create_seg_t(-1, -1, 0);
   }
   tree_t[cn].cc++;
   //cerr << "tree_t[" << cn << "].cc = " << tree_t[cn].cc << "\n";
   
   if(b == e) {
      //cerr << cn << " <---------------------\n\n";
      return cn;
   }

   int m = (b + e) / 2;
   //cerr << "cn = " << cn << "\n";
   if(i <= m) {
      tree_t[cn].L = upd_t(tree_t[cn].L, b, m, i);
      //cerr << "to left = " << tree_t[cn].L << "\n";
   } else {
      tree_t[cn].R = upd_t(tree_t[cn].R, m + 1, e, i);
      //cerr << "to right = " << tree_t[cn].R << "\n";
   }
   //cerr << cn << " --> " << tree_t[cn].L << " " << tree_t[cn].R << "\n";
   //cerr << cn << " <----------------\n\n";
   return cn;
}

int upd_t(int cn, int ti) {
   return upd_t(cn, 0, tvals.size() - 1, ti);
}

void upd(int si, int ti) {
   //cerr << si << " " << ti << "\n";
   si = svals.size() - si;
   while(si <= (int)svals.size()) {
      tree[si] = upd_t(tree[si], ti);
      si += si & (-si);
   }
}

void add(Score sc) {
   int si = lower_bound(svals.begin(), svals.end(), sc.s) - svals.begin();
   int ti = lower_bound(tvals.begin(), tvals.end(), sc.t) - tvals.begin();

   return upd(si, ti);
}

int calc(Query q) {
   int si = lower_bound(svals.begin(), svals.end(), q.a) - svals.begin();
   int ti = lower_bound(tvals.begin(), tvals.end(), q.b) - tvals.begin();
   return get(si, ti);
}

int main() {
   scanf("%d%d", &N, &Q);
   for(int i = 0; i < N; i++) {
      scanf("%d%d", &scores[i].s, &scores[i].t);
   }
   for(int i = 0; i < Q; i++) {
      scanf("%d%d%d", &queries[i].a, &queries[i].b, &queries[i].c);
      queries[i].i = i;
   }
   sort(scores, scores + N);
   sort(queries, queries + Q);


   compress();

   memset(tree, -1, sizeof tree);
   int i = 0;
   for(int q = 0; q < Q; q++) {
      while(i < N && scores[i].sum() >= queries[q].c) {
         add(scores[i]);
         i++;
      }
      res[queries[q].i] = calc(queries[q]);
   }

   for(int q = 0; q < Q; q++) {
      printf("%d\n", res[q]);
   }
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:138:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &N, &Q);
    ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:140:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d", &scores[i].s, &scores[i].t);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:143:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d%d", &queries[i].a, &queries[i].b, &queries[i].c);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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