oj.uz

Submission #934921

# Submission time Handle Problem Language Result Execution time Memory
934921 2024-02-28T07:49:32 Z oblantis Examination (JOI19_examination) C++17
0 / 100
 241 ms 17108 KB 
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e6 + 1;
typedef tree<int,
null_type,
less_equal<int>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
int n, q;
tuple<int, int, int, int> t[maxn];
int out[100000];
void ope(int l, int r){
	if(l + 1 == r)return;
	int mid = l + (r - l) / 2;
	ope(l, mid), ope(mid, r);
	vt<tuple<int, int, int, int>> ch;
	ordered_set os;
	int j = mid - 1, o = r - 1;
	while(j >= l && o >= mid){
		if(get<3>(t[j]) == 0)j--;
		else if(get<3>(t[o]) > 0)o--;
		else {
			if(get<1>(t[j]) <= get<1>(t[o])){
				os.insert(get<2>(t[o]));
				o--;
			}
			else {
				int x = os.size() - os.order_of_key(get<2>(t[j]));
				out[get<3>(t[j]) - 1] += x;
				j--;
			}
		}
	}
	while(j >= l){
		if(get<3>(t[j]) > 0){
			int x = os.size() - os.order_of_key(get<2>(t[j]));
			out[get<3>(t[j]) - 1] += x;
		}
		j--;
	}
	j = l, o = mid;
	while(j < mid || o < r){
		if(o == r || (j < mid && get<1>(t[j]) <= get<1>(t[o])))ch.pb(t[j++]);
		else ch.pb(t[o++]);
	}
	for(int i = l; i < r; i++){
		t[i] = ch[i - l];
	}
}
void solve() {
	cin >> n >> q;
	for(int i = 0, a, b; i < n; i++){
		cin >> a >> b;
		t[i] = make_tuple(a, b, a + b, 0);
	}
	for(int i = 0, a, b, c; i < q; i++){
		cin >> a >> b >> c;
		t[i + n] = make_tuple(a, b, c, i + 1);
	}
	sort(t, t + n + q);
	ope(0, n + q);
	for(int i = 0; i < q; i++)cout << out[i] << '\n';
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2516 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2512 KB Output is correct
7 Correct 6 ms 2892 KB Output is correct
8 Correct 7 ms 3068 KB Output is correct
9 Correct 6 ms 2888 KB Output is correct
10 Correct 6 ms 2888 KB Output is correct
11 Correct 6 ms 2888 KB Output is correct
12 Incorrect 5 ms 2652 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 16364 KB Output is correct
2 Correct 241 ms 17108 KB Output is correct
3 Correct 233 ms 16104 KB Output is correct
4 Correct 223 ms 15616 KB Output is correct
5 Correct 196 ms 16664 KB Output is correct
6 Incorrect 170 ms 15944 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 16364 KB Output is correct
2 Correct 241 ms 17108 KB Output is correct
3 Correct 233 ms 16104 KB Output is correct
4 Correct 223 ms 15616 KB Output is correct
5 Correct 196 ms 16664 KB Output is correct
6 Incorrect 170 ms 15944 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2516 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2512 KB Output is correct
7 Correct 6 ms 2892 KB Output is correct
8 Correct 7 ms 3068 KB Output is correct
9 Correct 6 ms 2888 KB Output is correct
10 Correct 6 ms 2888 KB Output is correct
11 Correct 6 ms 2888 KB Output is correct
12 Incorrect 5 ms 2652 KB Output isn't correct
13 Halted 0 ms 0 KB -