oj.uz

Submission #1099969

# Submission time Handle Problem Language Result Execution time Memory
1099969 2024-10-12T09:37:27 Z Nurislam Examination (JOI19_examination) C++17
100 / 100
 799 ms 87772 KB 
#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;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define ordst tree<int,  null_type,  less_equal<int>,  rb_tree_tag ,  tree_order_statistics_node_update >
template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}

const int N = 2e5+50, inf = LLONG_MAX;
//int mod = 998244353;
//int mod = 1000000007;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)
vector<ordst> t(N);
void upd(int i, int v){
	i = N-i-1;
	for(; i < N; i+= (i&-i))t[i].insert(v);
}
int get(int i, int v){
	int r = 0;
	i = N-i-1;
	for(;i>0; i-= (i&-i))r += (t[i].size() - t[i].order_of_key(v));
	return r;
}
void solve(){
	int n, m;
	cin >> n >> m;
	
	vector<array<int,2>>v(n);
	vector<int>a,b;
	vector<int>r,rt;
	for(int i = 0;i<n;i++){
		cin >> v[i][0] >> v[i][1];
		r.pb(v[i][1]);
		rt.pb(v[i][0]+v[i][1]);
	}
	
	sort(all(v));
	sort(all(r));
	sort(all(rt));
	for(int i = 0;i<n;i++){
		a.pb(v[i][1]);
		b.pb(v[i][1]+v[i][0]);
	}
	
	vector<array<int,4>> q(m);
	for(int i = 0;i<m;i++){
		cin >> q[i][0] >> q[i][1] >> q[i][2];
		q[i][3] = i; 
	}
	vector<int>ans(m);
	sort(rall(q));
	
	int cur = n - 1;
	
	for(int i = 0;i<m;i++){
		while(cur >= 0 && v[cur][0] >= q[i][0]){
			int x = lower_bound(all(r), a[cur]) - r.begin();
			int y = lower_bound(all(rt), b[cur]) - rt.begin();
			upd(x, y);
			cur -= 1;
		}
		int k = lower_bound(all(r), q[i][1]) - r.begin();
		int l = lower_bound(all(rt), q[i][2]) - rt.begin();
		ans[q[i][3]] = get(k, l);
		
	}
	
	for(auto to:ans)cout << to << "\n";
	
	
}
signed main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);cout.tie(NULL);
	int t = 1;
	//cin >> t;
	while(t--)
		solve();
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 9 ms 19020 KB Output is correct
3 Correct 10 ms 19036 KB Output is correct
4 Correct 10 ms 19228 KB Output is correct
5 Correct 10 ms 19032 KB Output is correct
6 Correct 11 ms 19228 KB Output is correct
7 Correct 17 ms 20568 KB Output is correct
8 Correct 17 ms 20568 KB Output is correct
9 Correct 16 ms 20572 KB Output is correct
10 Correct 15 ms 20572 KB Output is correct
11 Correct 15 ms 20732 KB Output is correct
12 Correct 13 ms 20572 KB Output is correct
13 Correct 15 ms 20616 KB Output is correct
14 Correct 15 ms 20572 KB Output is correct
15 Correct 15 ms 20572 KB Output is correct
16 Correct 13 ms 20572 KB Output is correct
17 Correct 13 ms 19804 KB Output is correct
18 Correct 11 ms 19556 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 82932 KB Output is correct
2 Correct 641 ms 85224 KB Output is correct
3 Correct 643 ms 85224 KB Output is correct
4 Correct 381 ms 81240 KB Output is correct
5 Correct 370 ms 84712 KB Output is correct
6 Correct 313 ms 86360 KB Output is correct
7 Correct 604 ms 85224 KB Output is correct
8 Correct 616 ms 85276 KB Output is correct
9 Correct 561 ms 85224 KB Output is correct
10 Correct 247 ms 84456 KB Output is correct
11 Correct 94 ms 36068 KB Output is correct
12 Correct 112 ms 35304 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 82932 KB Output is correct
2 Correct 641 ms 85224 KB Output is correct
3 Correct 643 ms 85224 KB Output is correct
4 Correct 381 ms 81240 KB Output is correct
5 Correct 370 ms 84712 KB Output is correct
6 Correct 313 ms 86360 KB Output is correct
7 Correct 604 ms 85224 KB Output is correct
8 Correct 616 ms 85276 KB Output is correct
9 Correct 561 ms 85224 KB Output is correct
10 Correct 247 ms 84456 KB Output is correct
11 Correct 94 ms 36068 KB Output is correct
12 Correct 112 ms 35304 KB Output is correct
13 Correct 684 ms 85888 KB Output is correct
14 Correct 626 ms 85736 KB Output is correct
15 Correct 635 ms 85460 KB Output is correct
16 Correct 477 ms 82900 KB Output is correct
17 Correct 381 ms 84976 KB Output is correct
18 Correct 303 ms 82148 KB Output is correct
19 Correct 762 ms 85728 KB Output is correct
20 Correct 702 ms 85768 KB Output is correct
21 Correct 799 ms 85704 KB Output is correct
22 Correct 290 ms 84292 KB Output is correct
23 Correct 98 ms 36100 KB Output is correct
24 Correct 119 ms 35308 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 9 ms 19020 KB Output is correct
3 Correct 10 ms 19036 KB Output is correct
4 Correct 10 ms 19228 KB Output is correct
5 Correct 10 ms 19032 KB Output is correct
6 Correct 11 ms 19228 KB Output is correct
7 Correct 17 ms 20568 KB Output is correct
8 Correct 17 ms 20568 KB Output is correct
9 Correct 16 ms 20572 KB Output is correct
10 Correct 15 ms 20572 KB Output is correct
11 Correct 15 ms 20732 KB Output is correct
12 Correct 13 ms 20572 KB Output is correct
13 Correct 15 ms 20616 KB Output is correct
14 Correct 15 ms 20572 KB Output is correct
15 Correct 15 ms 20572 KB Output is correct
16 Correct 13 ms 20572 KB Output is correct
17 Correct 13 ms 19804 KB Output is correct
18 Correct 11 ms 19556 KB Output is correct
19 Correct 598 ms 82932 KB Output is correct
20 Correct 641 ms 85224 KB Output is correct
21 Correct 643 ms 85224 KB Output is correct
22 Correct 381 ms 81240 KB Output is correct
23 Correct 370 ms 84712 KB Output is correct
24 Correct 313 ms 86360 KB Output is correct
25 Correct 604 ms 85224 KB Output is correct
26 Correct 616 ms 85276 KB Output is correct
27 Correct 561 ms 85224 KB Output is correct
28 Correct 247 ms 84456 KB Output is correct
29 Correct 94 ms 36068 KB Output is correct
30 Correct 112 ms 35304 KB Output is correct
31 Correct 684 ms 85888 KB Output is correct
32 Correct 626 ms 85736 KB Output is correct
33 Correct 635 ms 85460 KB Output is correct
34 Correct 477 ms 82900 KB Output is correct
35 Correct 381 ms 84976 KB Output is correct
36 Correct 303 ms 82148 KB Output is correct
37 Correct 762 ms 85728 KB Output is correct
38 Correct 702 ms 85768 KB Output is correct
39 Correct 799 ms 85704 KB Output is correct
40 Correct 290 ms 84292 KB Output is correct
41 Correct 98 ms 36100 KB Output is correct
42 Correct 119 ms 35308 KB Output is correct
43 Correct 668 ms 87768 KB Output is correct
44 Correct 646 ms 87772 KB Output is correct
45 Correct 648 ms 87636 KB Output is correct
46 Correct 471 ms 81132 KB Output is correct
47 Correct 370 ms 86244 KB Output is correct
48 Correct 314 ms 79856 KB Output is correct
49 Correct 758 ms 87628 KB Output is correct
50 Correct 693 ms 87748 KB Output is correct
51 Correct 774 ms 87524 KB Output is correct
52 Correct 341 ms 85984 KB Output is correct
53 Correct 147 ms 36832 KB Output is correct