Submission #557299

#	Time	Username	Problem	Language	Result	Execution time	Memory
557299		Ai7081	Examination (JOI19_examination)	C++17	100 / 100	1947 ms	124040 KiB

examination

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

const int N = 1e5 + 5;

struct query{
    int x, y, z, idx;
    bool operator < (const query &o) const {return z > o.z;}
};

struct score{
    int a, b;
    bool operator < (const score &o) const {return a+b > o.a+o.b;}
};

int n, t, fenA[N], fenB[N], timer, now, ans[N];
score s[N];
query q[N];
vector<int> fen[N];
set<int> fen_st[N], A, B;
map<int, int> mpA, mpB, mp_fen[N];

void add_set(int i, int val) {
    for (; i<N; i+=i&(-i)) fen_st[i].insert(val);
}

void add(int idx) {
    int i = mpA[s[idx].a];
    for (; i<=A.size(); i+=i&(-i)) {
        fenA[i]++;
        int j = mp_fen[i][s[idx].b];
        for (; j<=mp_fen[i].size(); j+=j&(-j)) fen[i][j]++;
    }
    i = mpB[s[idx].b];
    for (; i<=B.size(); i+=i&(-i)) fenB[i]++;
}

int query(int x, int y) {
    int ret = now;
    auto it = mpA.lower_bound(x);
    if (it != mpA.begin()) {
        int i = mpA[(--it)->first];
        for (; i>0; i-=i&(-i)) {
            ret -= fenA[i];
            it = mp_fen[i].lower_bound(y);
            if (it != mp_fen[i].begin()) {
                int j = mp_fen[i][(--it)->first];
                for (; j>0; j-=j&(-j)) ret += fen[i][j];
            }
        }
    }
    it = mpB.lower_bound(y);
    if (it != mpB.begin()) {
        int i = mpB[(--it)->first];
        for (; i>0; i-=i&(-i)) ret -= fenB[i];
    }
    return ret;
}

int main() {
    scanf(" %d %d", &n, &t);
    for (int i=0; i<n; i++) scanf(" %d %d", &s[i].a, &s[i].b);
    for (int i=0; i<t; i++) scanf(" %d %d %d", &q[i].x, &q[i].y, &q[i].z), q[i].idx = i;
    sort(s, s+n);
    sort(q, q+t);

    // build fenwick tree
    for (int i=0; i<n; i++) A.insert(s[i].a), B.insert(s[i].b);
    timer = 0;
    for (auto it : A) mpA[it] = ++timer;
    timer = 0 ;
    for (auto it : B) mpB[it] = ++timer;
    for (int i=0; i<n; i++) add_set(mpA[s[i].a], s[i].b);
    for (int i=1; i<=mpA.size(); i++) {
        fen[i].assign(fen_st[i].size()+5, 0);
        timer = 0;
        for (auto it : fen_st[i]) mp_fen[i][it] = ++timer;
    }

    // do query
    for (int i=0; i<t; i++) {
        while (now < n && s[now].a + s[now].b >= q[i].z) add(now++);
        ans[q[i].idx] = query(q[i].x, q[i].y);
    }
    for (int i=0; i<n; i++) printf("%d\n", ans[i]);
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void add(int)':
examination.cpp:29:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (; i<=A.size(); i+=i&(-i)) {
      |            ~^~~~~~~~~~
examination.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (; j<=mp_fen[i].size(); j+=j&(-j)) fen[i][j]++;
      |                ~^~~~~~~~~~~~~~~~~~
examination.cpp:35:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (; i<=B.size(); i+=i&(-i)) fenB[i]++;
      |            ~^~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i=1; i<=mpA.size(); i++) {
      |                   ~^~~~~~~~~~~~
examination.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf(" %d %d", &n, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
examination.cpp:62:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     for (int i=0; i<n; i++) scanf(" %d %d", &s[i].a, &s[i].b);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:63:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     for (int i=0; i<t; i++) scanf(" %d %d %d", &q[i].x, &q[i].y, &q[i].z), q[i].idx = i;
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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