Submission #873280

#	Time	Username	Problem	Language	Result	Execution time	Memory
873280		bobbilyking	Examination (JOI19_examination)	C++17	0 / 100	3052 ms	256100 KiB

examination

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

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

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)

#define NN 100010
#define M 1000000007 // 998244353

//GCC extensions
#include <bits/extc++.h>
using namespace __gnu_cxx;
using namespace __gnu_pbds;

struct query_multiset {
    // multiset that keeps track of things above you (basically oset)
    map<ll, ll> cnts;
    
    // order stats tree
    // find_by_order(i) returns ptr
    // order_of_key(key) return int
    typedef tree<pl, null_type, less<pl>,
    rb_tree_tag, tree_order_statistics_node_update> set_t;

    set_t oset;

    void insert(ll i) {
        oset.insert(pl{i, ++cnts[i]});
    }   

    // returns how many elements >= i
    ll query(ll i) {
        return oset.size() - oset.order_of_key(pl{i, -1});
    }
};

namespace mstree {
    query_multiset t[2 * NN];
    vector<ll> items; 
    ll n;

    ll f(ll i, ll k) { 

        cout << "Im querying " << k << ": " << t[i].query(k) << endl;
        for (const auto &[k, v]: t[i].cnts) cout << k << ", " << v << endl;

        return t[i].query(k);
    }
    void init() {
        sort(A(items));
        items.erase(unique(A(items)), items.end());
        n = items.size();
    }

    void add(ll a, ll b) {
        // A should always be in items
        ll idx = lower_bound(A(items), a) - items.begin();        
        
        idx += n;
        for (t[idx].insert(b); idx/=2;) t[idx].insert(b);
    } 
    
    ll i_query(ll l, ll r, ll k) { //num elements < k in interval [l, r)
        ll res = 0;
        for(l += n, r += n; l < r; l /= 2, r /= 2) {
            if(l & 1) res += f(l++, k);
            if(r & 1) res += f(--r, k);
        }
        return res;
    }

    ll query(ll a, ll b) {
        // a isn't necessarily guranteed to be in items
        ll suff = ll(lower_bound(A(items), a) - items.begin());

        // cout << "query " << a << " " << b << endl;
        // for (auto x: items) cout << x << " " ; cout << endl;
        // cout << suff << ", " << a << endl;

        return i_query(suff, n, b);
    }

}

int main(){
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);

    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(20);
    G(n) G(qn)
    vector<pair<ll, array<ll, 3>>> q;
    vector<pl> students;
    F(i, 0, n) {
        G(x) G(y) students.emplace_back(x, y); mstree::items.push_back(x);
    }
    mstree::init();
    sort(A(students), [](const auto &a, const auto &b) {
        return a.K + a.V > b.K + b.V;
    });

    F(i, 0, qn) {
        array<ll, 3> arr; F(i, 0, 3) cin >> arr[i];
        q.emplace_back(i, arr);
    }
    vector<ll> ans(qn);
    sort(A(q), [](const auto &a, const auto &b) {
        return a.V[2] > b.V[2];
    });

    ll fp = 0;
    for (const auto &[qidx, qarr]: q) {
        auto &[a, b, c] = qarr;
        while (fp < n && students[fp].K + students[fp].V >= c) {
            mstree::add(students[fp].K, students[fp].V);
            fp++;
        }
        
        ans[qidx] = mstree::query(a, b);
    }

    for (auto x: ans) cout << x << '\n';
}

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