Submission #391648

#	Time	Username	Problem	Language	Result	Execution time	Memory
391648		apostoldaniel854	Examination (JOI19_examination)	C++14	0 / 100	813 ms	54888 KiB

examination

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
typedef
tree<
  int,
  null_type,
  less<int>,
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;


using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n"

const int UPDATE = 1, QUERY = 2;

struct event_t {
    int total;
    int math;
    int info;
    int id;
    int type;
    bool operator < (const event_t &other) const {
        if (total != other.total)
            return total < other.total;
        return type < other.type;
    }
};

class fenwick2d {
public:
    int n;
    std::vector <ordered_set> aib;
    fenwick2d (int n) {
        this->n = n;
        aib.resize (1 + n);
    }
    void update (int x, int y) {
        while (x > 0) {
            aib[x].insert (y);
            x -= x & -x;
        }
    }
    int query (int x, int y) {
        int ans = 0;
        while (x <= n) {
            ans += aib[x].order_of_key (y + 1);
            x += x & -x;
        }
        return ans;
    }
};
const int MAX_N = 1e6;
int sol[1 + MAX_N];

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n, q;
    map <int, int> norm;
    cin >> n >> q;
    vector <event_t> events;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        events.push_back ({x + y, x, y, i, UPDATE});
        norm[x];
    }
    for (int i = 1; i <= q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        events.push_back ({z, x, y, i, QUERY});
        norm[x];
    }
    int tag = 0;
    for (auto &x : norm)
        x.second = ++tag;
    sort (events.begin (), events.end ());
    fenwick2d table (tag);
    for (event_t event : events) {
        if (event.type == UPDATE) {
            table.update (norm[event.math], event.info);
        }
        else {
            sol[event.id] = table.query (norm[event.math], event.info);
        }
    }
    for (int i = 1; i <= q; i++)
        cout << sol[i] << "\n";
    return 0;
}

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