Submission #557298

#	Time	Username	Problem	Language	Result	Execution time	Memory
557298		Ai7081	Examination (JOI19_examination)	C++17	100 / 100	2113 ms	126204 KiB

examination

#include <bits/stdc++.h>
using namespace std;
const bool debug = 0;

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];
        if (debug) printf("add %d %d\n", i, j);
        for (; j<=mp_fen[i].size(); j+=j&(-j)) fen[i][j]++;
    }
    if (debug) printf("add 1&2\n");
    i = mpB[s[idx].b];
    for (; i<=B.size(); i+=i&(-i)) fenB[i]++;
}

int query(int x, int y) {
    int ret = now;
    if (debug) printf("query now = %d\n", ret);
    auto it = mpA.lower_bound(x);
    if (it != mpA.begin()) {
        int i = mpA[(--it)->first];
        for (; i>0; i-=i&(-i)) {
            ret -= fenA[i];
            if (debug) printf("query - fenA[%d] = %d\n", i, ret);
            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];
                if (debug) printf("qeury %d %d = %d\n", i, j, ret);
            }
        }
    }
    it = mpB.lower_bound(y);
    if (it != mpB.begin()) {
        int i = mpB[(--it)->first];
        for (; i>0; i-=i&(-i)) ret -= fenB[i];
        if (debug) printf("query -fenB = %d\n", ret);
    }
    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);
    if (debug) {
        printf("sorted score\n");
        for (int i=0; i<n; i++) printf("a %d b %d\n", s[i].a, s[i].b);
        printf("sorted query\n");
        for (int i=0; i<t; i++) printf("x %d y %d z %d idx %d\n", q[i].x, q[i].y, q[i].z, q[i].idx);
    }

    // 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;
    if (debug) {
        printf("mpA : ");
        for (auto [key,val] : mpA) printf("(%d %d) ", key, val);
        printf("\n");
        printf("mpB : ");
        for (auto [key,val] : mpB) printf("(%d %d) ", key, val);
        printf("\n");
    }
    for (int i=0; i<n; i++) add_set(mpA[s[i].a], s[i].b);
    if (debug) {
        for (int i=1; i<=n; i++) {
            printf("fen_st %d : ", i);
            for (auto it : fen_st[i]) printf("%d ", it);
            printf("\n");
        }
        printf("\t\tadd_set done\n");
    }
    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;
    }
    if (debug) {
        printf("\t\tbuild map and assign fenwick done\n");
    }

    // do query
    for (int i=0; i<t; i++) {
        while (now < n && s[now].a + s[now].b >= q[i].z) add(now++);
        if (debug) printf("\t\tadd for t = %d done\n", i);
        ans[q[i].idx] = query(q[i].x, q[i].y);
        if (debug) printf("\t\tquery for t = %d done\n", i);
        if (debug) printf("\t\tans %d : %d\n", q[i].idx, ans[q[i].idx]);
    }
    if (debug) printf("all done next is answer\n");
    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:30:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (; i<=A.size(); i+=i&(-i)) {
      |            ~^~~~~~~~~~
examination.cpp:34:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (; j<=mp_fen[i].size(); j+=j&(-j)) fen[i][j]++;
      |                ~^~~~~~~~~~~~~~~~~~
examination.cpp:38:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (; i<=B.size(); i+=i&(-i)) fenB[i]++;
      |            ~^~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for (int i=1; i<=mpA.size(); i++) {
      |                   ~^~~~~~~~~~~~
examination.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf(" %d %d", &n, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
examination.cpp:69:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     for (int i=0; i<n; i++) scanf(" %d %d", &s[i].a, &s[i].b);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:70:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     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