oj.uz

답안 #810656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810656 2023-08-06T13:46:42 Z OrazB Examination (JOI19_examination) C++14
0 / 100
 3000 ms 232636 KB 
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
#define pii pair <int, int>
// #define ordered_set tree<pair<pii,int>, null_type,less<pair<pii,int>>, rb_tree_tag,tree_order_statistics_node_update>
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pb push_back
#define ff first
#define ss second

const int N = 1e5+5;
int n, q;
int pos[N], s[N], t[N], ans[N];
int x[N], y[N], z[N], ind[N];
map <pii,int> f[3];


void add(int x, int y){
	for (int i = x; i <= N-5; i += i&(-i)){
		f[0][{i, -1}]++;
	}
	for (int i = y; i <= N-5; i += i&(-i)){
		f[1][{i, -1}]++;
	}
	for (int i = x; i <= N-5; i += i&(-i)){
		for (int j = y; j <= N-5; j += j&(-j)) f[2][{i, j}]++;
	}
}
int count(int x, int y){
	int cnt = 0;
	for (int i = x; i > 0; i -= i&(-i)){
		cnt += f[0][{i, -1}];
	}
	for (int i = y; i > 0; i -= i&(-i)){
		cnt += f[1][{i, -1}];
	}
	for (int i = x; i > 0; i -= i&(-i)){
		for (int j = y; j > 0; j -= j&(-j)) cnt -= f[2][{i, j}];
	}
	return cnt;
}

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++){
		cin >> s[i] >> t[i];
		pos[i] = i;
	}
	sort(pos+1,pos+n+1, [&](int x, int y){
		return (s[x]+t[x]) > (s[y]+t[y]); 
	});
	for (int i = 1; i <= q; i++){
		cin >> x[i] >> y[i] >> z[i];
		ind[i] = i;
	}
	sort(ind+1,ind+q+1, [&](int x, int y){
		return z[x] > z[y]; 
	});
	int l = 0;
	// ordered_set st;
	for (int i = 1; i <= q; i++){
		while(l < n and s[pos[l+1]]+t[pos[l+1]] >= z[ind[i]]){
			l++;
			add(s[pos[l]], t[pos[l]]);
		}
		ans[ind[i]] = l-count(x[ind[i]]-1, y[ind[i]]-1);
	}
	for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 3047 ms 340 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3062 ms 232636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3062 ms 232636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 3047 ms 340 KB Time limit exceeded
3 Halted 0 ms 0 KB -