Submission #791197

#	Time	Username	Problem	Language	Result	Execution time	Memory
791197		shoryu386	Examination (JOI19_examination)	C++17	100 / 100	1936 ms	491056 KiB

examination

#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 (stderr)

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

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57