oj.uz

Submission #791197

# Submission time Handle Problem Language Result Execution time Memory
791197 2023-07-23T14:44:23 Z shoryu386 Examination (JOI19_examination) C++17
100 / 100
 1936 ms 491056 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;

template <typename T>
using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename K, typename V>
using pbds_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T>
using pbds_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename K, typename V>
using pbds_multimap = tree<K, V, less_equal<K>, rb_tree_tag, tree_order_statistics_node_update>;
//FOR PBDS MULTISET/MAP, LOWER BOUND SWAPS WITH UPPER BOUND IN FUNCTION

struct node{
	int s, e;
	#define m ((s+e)>>1)
	node *l, *r;
	
	pbds_multiset<int> v;
	
	node(int _s, int _e){
		s =_s, e = _e; l = NULL; r = NULL;
		
		//lazy node create
	}
	
	void instL(){
		if (l == NULL && s != e) {l = new node(s, m);}
	}
	
	void instR(){
		if (r == NULL && s != e) {r = new node(m+1, e);}
	}
	
	void add(int y, int xy){
		v.insert(xy);
		if (s == e){
			return;
		}
		
		if (y <= m){
			instL();
			l->add(y, xy);
		}
		else{
			instR();
			r->add(y, xy);
		}
		
	}
	
	int query(int x, int xyCutoff){
		if (x == s){
			//int cnt = 0;
			//for (int i : v) if (i >= xyCutoff) cout << "Found: " << i << '\n', cnt++;
			//return cnt;
			return v.size() - v.order_of_key(xyCutoff);
		}
		
		if (x > m){
			instR();
			return r->query(x, xyCutoff);
		}
		instL(), instR();
		return l->query(x, xyCutoff) + r->query(m+1, xyCutoff);
	}
};

main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	//if this TLEs I will cri
	node st(0, 1000000007);
	
	pair<int, int> students[n]; for (int x = 0; x < n; x++) cin >> students[x].first >> students[x].second;
	sort(students, students+n);
	
	vector<int> queries[n]; //A, B, C, queryNum
	int A, B, C;
	for (int x = 0; x < q; x++){
		cin >> A >> B >> C;
		queries[x] = {A,B,C,x};
	}
	
	sort(queries, queries+q);
	reverse(queries, queries+q);
	
	int sptr = n-1; //next student
	int curx = INT_MAX/3;
	
	int ans[q];
	for (int x = 0; x < q; x++){
		curx = queries[x][0];
		//cerr << "Handling:" <<  queries[x][3] << '\n';
		while (sptr != -1 && students[sptr].first >= curx){
			//add in students[sptr]
			st.add(students[sptr].second, students[sptr].first + students[sptr].second);
			//cerr << "Add: " << students[sptr].first << ' ' << students[sptr].second << '\n'; 
			sptr--;
		}
		
		
		ans[queries[x][3]] = st.query(queries[x][1], queries[x][2]);
	}
	
	for (int x = 0; x < q; x++) cout << ans[x] << '\n';
	
}

Compilation message

examination.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main(){
      | ^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 324 KB Output is correct
7 Correct 24 ms 19156 KB Output is correct
8 Correct 29 ms 19276 KB Output is correct
9 Correct 30 ms 19272 KB Output is correct
10 Correct 16 ms 4948 KB Output is correct
11 Correct 20 ms 19152 KB Output is correct
12 Correct 20 ms 4912 KB Output is correct
13 Correct 27 ms 19244 KB Output is correct
14 Correct 23 ms 19156 KB Output is correct
15 Correct 22 ms 19248 KB Output is correct
16 Correct 19 ms 19212 KB Output is correct
17 Correct 14 ms 4924 KB Output is correct
18 Correct 19 ms 4804 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1506 ms 171936 KB Output is correct
2 Correct 1558 ms 172020 KB Output is correct
3 Correct 1559 ms 171948 KB Output is correct
4 Correct 782 ms 153248 KB Output is correct
5 Correct 720 ms 172008 KB Output is correct
6 Correct 716 ms 153136 KB Output is correct
7 Correct 1614 ms 172032 KB Output is correct
8 Correct 1529 ms 170288 KB Output is correct
9 Correct 1482 ms 170236 KB Output is correct
10 Correct 630 ms 171764 KB Output is correct
11 Correct 739 ms 153016 KB Output is correct
12 Correct 1405 ms 152800 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1506 ms 171936 KB Output is correct
2 Correct 1558 ms 172020 KB Output is correct
3 Correct 1559 ms 171948 KB Output is correct
4 Correct 782 ms 153248 KB Output is correct
5 Correct 720 ms 172008 KB Output is correct
6 Correct 716 ms 153136 KB Output is correct
7 Correct 1614 ms 172032 KB Output is correct
8 Correct 1529 ms 170288 KB Output is correct
9 Correct 1482 ms 170236 KB Output is correct
10 Correct 630 ms 171764 KB Output is correct
11 Correct 739 ms 153016 KB Output is correct
12 Correct 1405 ms 152800 KB Output is correct
13 Correct 1659 ms 171976 KB Output is correct
14 Correct 1678 ms 171948 KB Output is correct
15 Correct 1588 ms 172040 KB Output is correct
16 Correct 849 ms 153148 KB Output is correct
17 Correct 742 ms 171900 KB Output is correct
18 Correct 692 ms 153084 KB Output is correct
19 Correct 1651 ms 171844 KB Output is correct
20 Correct 1824 ms 171984 KB Output is correct
21 Correct 1775 ms 171232 KB Output is correct
22 Correct 647 ms 171796 KB Output is correct
23 Correct 721 ms 152988 KB Output is correct
24 Correct 1500 ms 152804 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 324 KB Output is correct
7 Correct 24 ms 19156 KB Output is correct
8 Correct 29 ms 19276 KB Output is correct
9 Correct 30 ms 19272 KB Output is correct
10 Correct 16 ms 4948 KB Output is correct
11 Correct 20 ms 19152 KB Output is correct
12 Correct 20 ms 4912 KB Output is correct
13 Correct 27 ms 19244 KB Output is correct
14 Correct 23 ms 19156 KB Output is correct
15 Correct 22 ms 19248 KB Output is correct
16 Correct 19 ms 19212 KB Output is correct
17 Correct 14 ms 4924 KB Output is correct
18 Correct 19 ms 4804 KB Output is correct
19 Correct 1506 ms 171936 KB Output is correct
20 Correct 1558 ms 172020 KB Output is correct
21 Correct 1559 ms 171948 KB Output is correct
22 Correct 782 ms 153248 KB Output is correct
23 Correct 720 ms 172008 KB Output is correct
24 Correct 716 ms 153136 KB Output is correct
25 Correct 1614 ms 172032 KB Output is correct
26 Correct 1529 ms 170288 KB Output is correct
27 Correct 1482 ms 170236 KB Output is correct
28 Correct 630 ms 171764 KB Output is correct
29 Correct 739 ms 153016 KB Output is correct
30 Correct 1405 ms 152800 KB Output is correct
31 Correct 1659 ms 171976 KB Output is correct
32 Correct 1678 ms 171948 KB Output is correct
33 Correct 1588 ms 172040 KB Output is correct
34 Correct 849 ms 153148 KB Output is correct
35 Correct 742 ms 171900 KB Output is correct
36 Correct 692 ms 153084 KB Output is correct
37 Correct 1651 ms 171844 KB Output is correct
38 Correct 1824 ms 171984 KB Output is correct
39 Correct 1775 ms 171232 KB Output is correct
40 Correct 647 ms 171796 KB Output is correct
41 Correct 721 ms 152988 KB Output is correct
42 Correct 1500 ms 152804 KB Output is correct
43 Correct 1936 ms 490556 KB Output is correct
44 Correct 1796 ms 491056 KB Output is correct
45 Correct 1771 ms 490668 KB Output is correct
46 Correct 1597 ms 153712 KB Output is correct
47 Correct 910 ms 490744 KB Output is correct
48 Correct 717 ms 153368 KB Output is correct
49 Correct 1913 ms 490964 KB Output is correct
50 Correct 1765 ms 456684 KB Output is correct
51 Correct 1742 ms 456572 KB Output is correct
52 Correct 682 ms 490816 KB Output is correct
53 Correct 1514 ms 152972 KB Output is correct