Submission #1253512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253512		quangminh412	Examination (JOI19_examination)	C++20	100 / 100	1478 ms	639448 KiB

examination

/*
  Ben Watson
  Handle codeforces : quangminh98

  Current Theme: Transformers !!!!
*/

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

#define ll long long

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
const int maxn = 1e5 + 1;
const int maxbit = 31;

struct Trie
{
    struct Node
    {
        Node* child[2];
        int cnt;

        Node() : cnt(0) { child[0] = child[1] = nullptr; }
    };
    Node* root;

    Trie() { root = new Node(); }

    void add(int x)
    {
        Node* p = root;
        for (int i = maxbit - 1; i >= 0; i--)
        {
            int bit = (x >> i & 1);
            if (p->child[bit] == nullptr)
                p->child[bit] = new Node();

            p = p->child[bit];
            p->cnt++;
        }
    }
//
//    void del(int x)
//    {
//        Node* p = root;
//        vector<pair<Node*, int>> paths;
//        for (int i = maxbit - 1; i >= 0; i--)
//        {
//            int bit = (x >> i & 1);
//
//            paths.push_back({p, bit});
//            p = p->child[bit];
//            p->cnt--;
//        }
//        int m = paths.size();
//        for (int i = m - 1; i >= 0; i--)
//        {
//            int bit = paths[i].second;
//            Node *par = paths[i].first;
//            Node *son = par->child[bit];
//
//            if (son->cnt == 0)
//            {
//                delete(son);
//                par->child[bit] = nullptr;
//            } else
//                break;
//        }
//    }

    int query(int x) // count all integers >= x
    {
        int res = 0;
        Node* p = root;
        for (int i = maxbit - 1; i >= 0; i--)
        {
            int bit = (x >> i & 1);
            if (bit == 0 && p->child[1] != nullptr)
                res += p->child[1]->cnt;

            if (p->child[bit] == nullptr)
                return res;
            p = p->child[bit];
        }
        res += p->cnt;
        return res;
    }
};

struct FenwickTree
{
    vector<Trie> bits;
    int n;

    FenwickTree(int n) : n(n) { bits.resize(n + 1); }

    void update(int pos, int val)
    {
        for (; pos <= n; pos += (pos & (-pos)))
            bits[pos].add(val);
    }

    int query(int pos, int x)
    {
        int res = 0;
        for (; pos > 0; pos -= (pos & (-pos)))
            res += bits[pos].query(x);
        return res;
    }
    int query(int l, int r, int x) { return query(r, x) - query(l - 1, x); }
};

int n, q;
pair<int, int> students[maxn];
vector<array<int, 4>> queries;

// coordinate compression and sqrt decomposition on it
int cur, num;
vector<int> v;
map<int, int> cmp;
//int block_id[maxn];

void solve()
{
    cin >> n >> q;
    vector<pair<int, int>> proc;
    for (int i = 1; i <= n; i++)
    {
        cin >> students[i].first >> students[i].second;
        v.push_back(students[i].first);
        proc.push_back({students[i].first + students[i].second, i});
    }

    cur = 0;
    sort(v.begin(), v.end());
    for (int x : v)
        if (cmp[x] == 0)
            cmp[x] = ++cur;
//    num = 0;
//    for (int i = 1; i <= cur; i++)
//    {
//        if ((i - 1) % N == 0)
//            num++;
//        block_id[i] = num;
//    }

    for (int i = 0; i < q; i++)
    {
        int x, y, z; cin >> x >> y >> z;
        queries.push_back({z, x, y, i});
    }

    sort(proc.begin(), proc.end(), greater<pair<int, int>>());
    sort(queries.begin(), queries.end(), greater<array<int, 4>>());

    int pos = 0;
    vector<int> ans(q);
    FenwickTree bit(cur);
    for (array<int, 4> Q : queries)
    {
        int z = Q[0], x = Q[1], y = Q[2], id = Q[3];

        while (pos < n && proc[pos].first >= z)
        {
            int i = proc[pos].second;
            bit.update(cmp[students[i].first], students[i].second);
            pos++;
        }

        int i = lower_bound(v.begin(), v.end(), x) - v.begin();
        if (i == v.size())
            ans[id] = 0;
        else
        {
            int l = v[i];
            ans[id] = bit.query(cmp[l], cur, y);
        }
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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