oj.uz

Submission #384310

# Submission time Handle Problem Language Result Execution time Memory
384310 2021-04-01T10:32:10 Z amoo_safar Examination (JOI19_examination) C++17
2 / 100
 3000 ms 71120 KB 
// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 998244353;
const int N = 1e5 + 10;
const int Inf = 2000000100;
const ll Log = 30;

typedef pair<int, int> pii;

struct Segment {
	int n = 0;
	vector<pii> V;
	vector<int> seg[N << 2];

	void Add(pii X){
		V.pb(X);
		return ;
	}
	void Build(int id, int L, int R){
		for(int i = L; i < R; i++) seg[id].pb(V[i].S);
		sort(all(seg[id]));
		if(L + 1 == R) return ;
		int mid = (L + R) >> 1;
		Build(id << 1, L, mid);
		Build(id<<1|1, mid, R);
	}
	int Get(int id, int l, int r, int lw, int hg, int L, int R){
		if(r <= L || R <= l) return 0;
		if(l <= L && R <= r){
			return lower_bound(all(seg[id]), hg + 1) - lower_bound(all(seg[id]), lw);
		}
		int mid = (L + R) >> 1;
		return Get(id << 1, l, r, lw, hg, L, mid) + Get(id << 1 | 1, l, r, lw, hg, mid, R);
	}
	int GetRect(int lx, int rx, int ly, int ry){ // [], []
		// lx = lower_bound(all(V), pii(lx, -Inf)) - V.begin();
		// rx = lower_bound(all(V), pii(rx, Inf)) - V.begin();
		int sm = 0;
		for(auto [x, y] : V)
			if(lx <= x && x <= rx && ly <= y && y <= ry) sm ++;
		return sm;

		return Get(1, lx, rx, ly, ry, 0, n);
	}
	void init(){
		n = V.size();
		sort(all(V));
		Build(1, 0, n);
	}
};
Segment SX, SY, XY;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, q;
	cin >> n >> q;
	int x, y;
	vector<int> U;
	for(int i = 0; i < n; i++){
		cin >> x >> y;
		SX.Add({x + y, x});
		SY.Add({x + y, y});
		XY.Add({x, y});
		U.pb(x + y);
	}
	sort(all(U));
	SX.init();
	SY.init();
	XY.init();

	int a, b, c;
	for(int i = 0; i < q; i++){
		cin >> a >> b >> c;
		if(a + b >= c){
			cout << XY.GetRect(a, Inf, b, Inf) << '\n';
			continue;
		}
		int und = lower_bound(all(U), c) - U.begin();
		int lf = SX.GetRect(c, Inf, 0, a - 1);
		int rt = SY.GetRect(c, Inf, 0, b - 1);
		cout << n - und - lf - rt << '\n';
	}
	return 0;
}
/*
5 1
1 2
2 3
3 4
1 5

*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28524 KB Output is correct
2 Correct 20 ms 28524 KB Output is correct
3 Correct 20 ms 28524 KB Output is correct
4 Correct 20 ms 28524 KB Output is correct
5 Correct 20 ms 28524 KB Output is correct
6 Correct 20 ms 28524 KB Output is correct
7 Correct 54 ms 29804 KB Output is correct
8 Correct 54 ms 29804 KB Output is correct
9 Correct 58 ms 29828 KB Output is correct
10 Correct 52 ms 29676 KB Output is correct
11 Correct 48 ms 29676 KB Output is correct
12 Correct 46 ms 29676 KB Output is correct
13 Correct 54 ms 29804 KB Output is correct
14 Correct 54 ms 29824 KB Output is correct
15 Correct 54 ms 29804 KB Output is correct
16 Correct 42 ms 29676 KB Output is correct
17 Correct 47 ms 29676 KB Output is correct
18 Correct 49 ms 29676 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 71120 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 3052 ms 71120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28524 KB Output is correct
2 Correct 20 ms 28524 KB Output is correct
3 Correct 20 ms 28524 KB Output is correct
4 Correct 20 ms 28524 KB Output is correct
5 Correct 20 ms 28524 KB Output is correct
6 Correct 20 ms 28524 KB Output is correct
7 Correct 54 ms 29804 KB Output is correct
8 Correct 54 ms 29804 KB Output is correct
9 Correct 58 ms 29828 KB Output is correct
10 Correct 52 ms 29676 KB Output is correct
11 Correct 48 ms 29676 KB Output is correct
12 Correct 46 ms 29676 KB Output is correct
13 Correct 54 ms 29804 KB Output is correct
14 Correct 54 ms 29824 KB Output is correct
15 Correct 54 ms 29804 KB Output is correct
16 Correct 42 ms 29676 KB Output is correct
17 Correct 47 ms 29676 KB Output is correct
18 Correct 49 ms 29676 KB Output is correct
19 Execution timed out 3052 ms 71120 KB Time limit exceeded
20 Halted 0 ms 0 KB -