Submission #701075

#	Time	Username	Problem	Language	Result	Execution time	Memory
701075		badont	Examination (JOI19_examination)	C++17	100 / 100	2577 ms	27504 KiB

examination

//60 J O
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <memory>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using ll = int;
using ld = long double;
using pii = pair<ll,ll>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T>
struct fen {
	vector<T> tr;
	ll mxn;

	fen(ll sz) {
		mxn = sz;
		tr.assign(sz + 5, 0);
	}

	void upd(ll g, T k) {
	    g++;	
        assert(g != 0);
		for (; g <= mxn; g += g&-g)
			tr[g] += k;
	}

	T ge(ll g) {
        g++;
		T res = 0;
		for (; g; g -= g&-g)
			res += tr[g];
		return res;
	}

	T rng(ll l, ll r) { return ge(r) - ge(l - 1); }

};

//var 
ll T;

void solve() {
    ll n, q;
    cin >> n >> q;

    vector<ll> ricky_y, ricky_x;
    vector<array<ll, 3>> order;
    
    F0R (i, n) {
        ll x, y;
        cin >> x >> y;
        order.pb({1, x, y});
        ricky_y.pb(y);
        ricky_x.pb(x);
    }

    vector<ll> ans(q);
    vector<array<ll, 3>> queries(q);

    for (auto& [x, y, z] : queries)
        cin >> x >> y >> z;

    F0R (i, q) {
        auto& [x, y, c] = queries[i];
        order.pb({2, i, c});
        ricky_y.pb(y);
        ricky_x.pb(x);
    }


    sort(all(order), [&](const array<ll,3>& a, const array<ll,3>& b) {
        ll ca = (a[0] == 1 ? a[1] + a[2] : a[2]);
        ll cb = (b[0] == 1 ? b[1] + b[2] : b[2]);
        if (ca == cb) return a[0] < b[0];
        return ca > cb;
    });

    sort(all(ricky_y));
    ricky_y.erase(unique(all(ricky_y)), ricky_y.end());

    sort(all(ricky_x));
    ricky_x.erase(unique(all(ricky_x)), ricky_x.end());

    auto get_y = [&ricky_y](ll x) -> ll {
        return lower_bound(all(ricky_y), x) - ricky_y.begin();
    };

    auto get_x = [&ricky_x](ll x) -> ll {
        return lower_bound(all(ricky_x), x) - ricky_x.begin();
    };

    ll Y = (int)ricky_y.size();
    ll X = (int)ricky_x.size();

    debug(queries);
    
    constexpr int B = 550;
    vector active_points(X, vector<ll>());
    for (ll query_start = 0; query_start < (int)order.size(); query_start += B) {
        vector<array<ll, 3>> process_here;
        for (int i = query_start; i < min((ll)order.size(), query_start + B); i++) {
            process_here.pb(order[i]);
        }

        debug(process_here);

        //local batch
        for (int i = 0; i < (int)process_here.size(); i++) {
            auto& [T1, a1, b1] = process_here[i];
            for (int j = i + 1; j < (int)process_here.size(); j++) {
                auto& [T2, a2, b2] = process_here[j];
                if (T1 == 1 and T2 == 2) {
                    //T2 has a lesser line fo sho
                    auto& [gx, gy, line] = queries[a2];
                    if (a1 >= gx and b1 >= gy) {
                        ans[a2]++;
                    }
                }
            }
        }

        //global batch
        //sort(all(active_points), greater<pii>());
        int cur_pt = 0;

        vector agg_by_x(X, vector<ll>());
        for (auto [T, a1, b1] : process_here) if (T == 2) {
            agg_by_x[get_x(queries[a1][0])].pb(a1);
        }

        fen<int> tree(Y);
        ll big = 0;
        for (int x = X - 1; x >= 0; x--) {
            for (auto& y : active_points[x]) {
                tree.upd(y, 1);
                big++;
            }

            for (auto& qid : agg_by_x[x]) {
                ll y = get_y(queries[qid][1]);
                ans[qid] += big - tree.ge(y - 1);
            }
        }

        //update global
        for (auto& [T, a1, b1] : process_here) if (T == 1) {
            active_points[get_x(a1)].pb(get_y(b1));
        }
    }

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

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void solve()':
examination.cpp:44:20: warning: statement has no effect [-Wunused-value]
   44 | #define debug(...) "zzz"
      |                    ^~~~~
examination.cpp:144:5: note: in expansion of macro 'debug'
  144 |     debug(queries);
      |     ^~~~~
examination.cpp:44:20: warning: statement has no effect [-Wunused-value]
   44 | #define debug(...) "zzz"
      |                    ^~~~~
examination.cpp:154:9: note: in expansion of macro 'debug'
  154 |         debug(process_here);
      |         ^~~~~
examination.cpp:173:13: warning: unused variable 'cur_pt' [-Wunused-variable]
  173 |         int cur_pt = 0;
      |             ^~~~~~

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