oj.uz

Submission #701071

# Submission time Handle Problem Language Result Execution time Memory
701071 2023-02-20T02:51:53 Z badont Examination (JOI19_examination) C++17
2 / 100
 3000 ms 16080 KB 
//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 = long long;
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;
    vector<array<ll, 3>> order;
    
    F0R (i, n) {
        ll x, y;
        cin >> x >> y;
        order.pb({1, x, y});
        ricky_y.pb(y);
    }

    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);
    }


    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());

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

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

    debug(queries);
    
    constexpr int B = 469;
    vector<pii> active_points;
    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<ll> global_agg;
        for (auto& [T, idx, __] : process_here) if (T == 2) {
            global_agg.pb(idx);
        }

        sort(all(global_agg), [&](ll q1, ll q2) {
            return queries[q1][0] > queries[q2][0]; 
        });

        fen<int> tree(Y);
        
        for (auto qid : global_agg) {
            auto [x, y, __] = queries[qid];

            while (cur_pt < (int)active_points.size() and active_points[cur_pt].f >= x) {
                auto [nx, ny] = active_points[cur_pt];
                tree.upd(get_y(ny), 1);
                cur_pt++;
            }

            ans[qid] += tree.rng(get_y(y), Y - 1);
        }

        //update global
        for (auto& [T, a1, b1] : process_here) if (T == 1) {
            active_points.pb({a1, 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

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 9 ms 852 KB Output is correct
8 Correct 9 ms 852 KB Output is correct
9 Correct 9 ms 844 KB Output is correct
10 Correct 8 ms 844 KB Output is correct
11 Correct 9 ms 852 KB Output is correct
12 Correct 5 ms 716 KB Output is correct
13 Correct 7 ms 852 KB Output is correct
14 Correct 6 ms 852 KB Output is correct
15 Correct 7 ms 844 KB Output is correct
16 Correct 6 ms 848 KB Output is correct
17 Correct 6 ms 840 KB Output is correct
18 Correct 3 ms 724 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 16080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 16080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 9 ms 852 KB Output is correct
8 Correct 9 ms 852 KB Output is correct
9 Correct 9 ms 844 KB Output is correct
10 Correct 8 ms 844 KB Output is correct
11 Correct 9 ms 852 KB Output is correct
12 Correct 5 ms 716 KB Output is correct
13 Correct 7 ms 852 KB Output is correct
14 Correct 6 ms 852 KB Output is correct
15 Correct 7 ms 844 KB Output is correct
16 Correct 6 ms 848 KB Output is correct
17 Correct 6 ms 840 KB Output is correct
18 Correct 3 ms 724 KB Output is correct
19 Execution timed out 3060 ms 16080 KB Time limit exceeded
20 Halted 0 ms 0 KB -