oj.uz

Submission #701073

# Submission time Handle Problem Language Result Execution time Memory
701073 2023-02-20T03:01:43 Z badont Examination (JOI19_examination) C++17
43 / 100
 3000 ms 30164 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, 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 = 469;
    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);
        for (int x = X - 1; x >= 0; x--) {
            for (auto y : active_points[x]) {
                tree.upd(y, 1);
            }

            for (auto qid : agg_by_x[x]) {
                ans[qid] += tree.rng(get_y(queries[qid][1]), 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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 9 ms 1072 KB Output is correct
8 Correct 10 ms 1128 KB Output is correct
9 Correct 10 ms 1092 KB Output is correct
10 Correct 9 ms 1092 KB Output is correct
11 Correct 8 ms 820 KB Output is correct
12 Correct 5 ms 724 KB Output is correct
13 Correct 7 ms 1080 KB Output is correct
14 Correct 7 ms 1092 KB Output is correct
15 Correct 7 ms 1100 KB Output is correct
16 Correct 5 ms 724 KB Output is correct
17 Correct 8 ms 1092 KB Output is correct
18 Correct 3 ms 816 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1738 ms 18492 KB Output is correct
2 Correct 1736 ms 21000 KB Output is correct
3 Correct 1691 ms 20980 KB Output is correct
4 Correct 827 ms 21804 KB Output is correct
5 Correct 685 ms 16196 KB Output is correct
6 Correct 211 ms 15456 KB Output is correct
7 Correct 1457 ms 20224 KB Output is correct
8 Correct 1613 ms 20908 KB Output is correct
9 Correct 1411 ms 20364 KB Output is correct
10 Correct 612 ms 16044 KB Output is correct
11 Correct 636 ms 21656 KB Output is correct
12 Correct 245 ms 15084 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1738 ms 18492 KB Output is correct
2 Correct 1736 ms 21000 KB Output is correct
3 Correct 1691 ms 20980 KB Output is correct
4 Correct 827 ms 21804 KB Output is correct
5 Correct 685 ms 16196 KB Output is correct
6 Correct 211 ms 15456 KB Output is correct
7 Correct 1457 ms 20224 KB Output is correct
8 Correct 1613 ms 20908 KB Output is correct
9 Correct 1411 ms 20364 KB Output is correct
10 Correct 612 ms 16044 KB Output is correct
11 Correct 636 ms 21656 KB Output is correct
12 Correct 245 ms 15084 KB Output is correct
13 Correct 1368 ms 21408 KB Output is correct
14 Correct 1607 ms 21748 KB Output is correct
15 Correct 1710 ms 21388 KB Output is correct
16 Correct 793 ms 20244 KB Output is correct
17 Correct 618 ms 16672 KB Output is correct
18 Correct 227 ms 15456 KB Output is correct
19 Correct 1404 ms 21308 KB Output is correct
20 Correct 1532 ms 21312 KB Output is correct
21 Correct 1320 ms 20924 KB Output is correct
22 Correct 610 ms 15968 KB Output is correct
23 Correct 639 ms 21608 KB Output is correct
24 Correct 238 ms 15160 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 9 ms 1072 KB Output is correct
8 Correct 10 ms 1128 KB Output is correct
9 Correct 10 ms 1092 KB Output is correct
10 Correct 9 ms 1092 KB Output is correct
11 Correct 8 ms 820 KB Output is correct
12 Correct 5 ms 724 KB Output is correct
13 Correct 7 ms 1080 KB Output is correct
14 Correct 7 ms 1092 KB Output is correct
15 Correct 7 ms 1100 KB Output is correct
16 Correct 5 ms 724 KB Output is correct
17 Correct 8 ms 1092 KB Output is correct
18 Correct 3 ms 816 KB Output is correct
19 Correct 1738 ms 18492 KB Output is correct
20 Correct 1736 ms 21000 KB Output is correct
21 Correct 1691 ms 20980 KB Output is correct
22 Correct 827 ms 21804 KB Output is correct
23 Correct 685 ms 16196 KB Output is correct
24 Correct 211 ms 15456 KB Output is correct
25 Correct 1457 ms 20224 KB Output is correct
26 Correct 1613 ms 20908 KB Output is correct
27 Correct 1411 ms 20364 KB Output is correct
28 Correct 612 ms 16044 KB Output is correct
29 Correct 636 ms 21656 KB Output is correct
30 Correct 245 ms 15084 KB Output is correct
31 Correct 1368 ms 21408 KB Output is correct
32 Correct 1607 ms 21748 KB Output is correct
33 Correct 1710 ms 21388 KB Output is correct
34 Correct 793 ms 20244 KB Output is correct
35 Correct 618 ms 16672 KB Output is correct
36 Correct 227 ms 15456 KB Output is correct
37 Correct 1404 ms 21308 KB Output is correct
38 Correct 1532 ms 21312 KB Output is correct
39 Correct 1320 ms 20924 KB Output is correct
40 Correct 610 ms 15968 KB Output is correct
41 Correct 639 ms 21608 KB Output is correct
42 Correct 238 ms 15160 KB Output is correct
43 Correct 2616 ms 30136 KB Output is correct
44 Correct 2553 ms 30164 KB Output is correct
45 Execution timed out 3036 ms 29664 KB Time limit exceeded
46 Halted 0 ms 0 KB -