제출 #429586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429586		Return_0	Examination (JOI19_examination)	C++17	100 / 100	246 ms	5856 KiB

examination

#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

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

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< (x) << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 1e5 + 7;

struct fenwick {
	ll fen [N];
	fenwick () { memset(fen, 0, sizeof fen); }
	inline void add (ll i) { for (; i < N; i += i & -i) ++fen[i]; }
	inline ll ask (ll i) { ll t = 0; for (; i; i -= i & -i) t += fen[i]; return t; }
} fen [2];

ll A [N], B [N], X [N], Y [N], Z [N], id1 [N], id2 [N], ans [N], n, q;
vector <ll> vec [2];
inline ll Getx (cl &x) { return lower_bound(All(vec[0]), x) - vec[0].begin() + 1; }
inline ll Gety (cl &y) { return lower_bound(All(vec[1]), y) - vec[1].begin() + 1; }

int main ()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>> n >> q;
	for (ll i = 1; i <= n; i++) cin>> A[i] >> B[i], id1[i] = i, vec[0].push_back(A[i]), vec[1].push_back(B[i]);
	for (ll i = 1; i <= q; i++) cin>> X[i] >> Y[i] >> Z[i], Z[i] = max(Z[i], X[i] + Y[i]), id2[i] = i;

	sort(id1 + 1, id1 + n + 1, [&](cl &x, cl &y) { return A[x] + B[x] > A[y] + B[y]; });
	sort(id2 + 1, id2 + q + 1, [&](cl &x, cl &y) { return Z[x] > Z[y]; });
	sort(All(vec[0])); vec[0].resize(unique(All(vec[0])) - vec[0].begin());
	sort(All(vec[1])); vec[1].resize(unique(All(vec[1])) - vec[1].begin());

	for (ll i = 1, j, ptr = 1; i <= q; i++) {
		j = id2[i];
		for (; ptr <= n && A[id1[ptr]] + B[id1[ptr]] >= Z[j]; ptr++) fen[0].add(Getx(A[id1[ptr]])), fen[1].add(Gety(B[id1[ptr]]));
		ans[j] = ptr - fen[0].ask(Getx(X[j]) - 1) - fen[1].ask(Gety(Y[j]) - 1) - 1;
	}

	output(1, q, ans, 0);

	cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

	return 0;
}
/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100

10 10
41304 98327
91921 28251
85635 59191
30361 72671
28949 96958
99041 37826
10245 2726
19387 20282
60366 87723
95388 49726
52302 69501 66009
43754 45346 3158
25224 58881 18727
7298 24412 63782
24107 10583 61508
65025 29140 7278
36104 56758 2775
23126 67608 122051
56910 17272 62933
39675 15874 117117

*/

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