oj.uz

Submission #701074

# Submission time Handle Problem Language Result Execution time Memory
701074 2023-02-20T03:03:37 Z badont Examination (JOI19_examination) C++17
43 / 100
 3000 ms 23484 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 = 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 = 447;
    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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 11 ms 1052 KB Output is correct
8 Correct 10 ms 964 KB Output is correct
9 Correct 9 ms 876 KB Output is correct
10 Correct 8 ms 964 KB Output is correct
11 Correct 7 ms 468 KB Output is correct
12 Correct 4 ms 468 KB Output is correct
13 Correct 7 ms 964 KB Output is correct
14 Correct 7 ms 932 KB Output is correct
15 Correct 7 ms 968 KB Output is correct
16 Correct 4 ms 596 KB Output is correct
17 Correct 7 ms 992 KB Output is correct
18 Correct 3 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1789 ms 12872 KB Output is correct
2 Correct 1819 ms 14108 KB Output is correct
3 Correct 1865 ms 12756 KB Output is correct
4 Correct 932 ms 13776 KB Output is correct
5 Correct 783 ms 7672 KB Output is correct
6 Correct 236 ms 7704 KB Output is correct
7 Correct 1643 ms 12812 KB Output is correct
8 Correct 1801 ms 14040 KB Output is correct
9 Correct 1636 ms 12660 KB Output is correct
10 Correct 712 ms 7540 KB Output is correct
11 Correct 718 ms 13644 KB Output is correct
12 Correct 262 ms 7296 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1789 ms 12872 KB Output is correct
2 Correct 1819 ms 14108 KB Output is correct
3 Correct 1865 ms 12756 KB Output is correct
4 Correct 932 ms 13776 KB Output is correct
5 Correct 783 ms 7672 KB Output is correct
6 Correct 236 ms 7704 KB Output is correct
7 Correct 1643 ms 12812 KB Output is correct
8 Correct 1801 ms 14040 KB Output is correct
9 Correct 1636 ms 12660 KB Output is correct
10 Correct 712 ms 7540 KB Output is correct
11 Correct 718 ms 13644 KB Output is correct
12 Correct 262 ms 7296 KB Output is correct
13 Correct 1496 ms 12768 KB Output is correct
14 Correct 1673 ms 14280 KB Output is correct
15 Correct 1711 ms 14104 KB Output is correct
16 Correct 818 ms 13864 KB Output is correct
17 Correct 642 ms 7672 KB Output is correct
18 Correct 221 ms 7668 KB Output is correct
19 Correct 1422 ms 13768 KB Output is correct
20 Correct 1536 ms 14172 KB Output is correct
21 Correct 1311 ms 13368 KB Output is correct
22 Correct 699 ms 7628 KB Output is correct
23 Correct 694 ms 13656 KB Output is correct
24 Correct 257 ms 7296 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 11 ms 1052 KB Output is correct
8 Correct 10 ms 964 KB Output is correct
9 Correct 9 ms 876 KB Output is correct
10 Correct 8 ms 964 KB Output is correct
11 Correct 7 ms 468 KB Output is correct
12 Correct 4 ms 468 KB Output is correct
13 Correct 7 ms 964 KB Output is correct
14 Correct 7 ms 932 KB Output is correct
15 Correct 7 ms 968 KB Output is correct
16 Correct 4 ms 596 KB Output is correct
17 Correct 7 ms 992 KB Output is correct
18 Correct 3 ms 468 KB Output is correct
19 Correct 1789 ms 12872 KB Output is correct
20 Correct 1819 ms 14108 KB Output is correct
21 Correct 1865 ms 12756 KB Output is correct
22 Correct 932 ms 13776 KB Output is correct
23 Correct 783 ms 7672 KB Output is correct
24 Correct 236 ms 7704 KB Output is correct
25 Correct 1643 ms 12812 KB Output is correct
26 Correct 1801 ms 14040 KB Output is correct
27 Correct 1636 ms 12660 KB Output is correct
28 Correct 712 ms 7540 KB Output is correct
29 Correct 718 ms 13644 KB Output is correct
30 Correct 262 ms 7296 KB Output is correct
31 Correct 1496 ms 12768 KB Output is correct
32 Correct 1673 ms 14280 KB Output is correct
33 Correct 1711 ms 14104 KB Output is correct
34 Correct 818 ms 13864 KB Output is correct
35 Correct 642 ms 7672 KB Output is correct
36 Correct 221 ms 7668 KB Output is correct
37 Correct 1422 ms 13768 KB Output is correct
38 Correct 1536 ms 14172 KB Output is correct
39 Correct 1311 ms 13368 KB Output is correct
40 Correct 699 ms 7628 KB Output is correct
41 Correct 694 ms 13656 KB Output is correct
42 Correct 257 ms 7296 KB Output is correct
43 Correct 2558 ms 21764 KB Output is correct
44 Correct 2574 ms 23484 KB Output is correct
45 Execution timed out 3053 ms 22868 KB Time limit exceeded
46 Halted 0 ms 0 KB -