Submission #208607

#	Time	Username	Problem	Language	Result	Execution time	Memory
208607		erd1	Examination (JOI19_examination)	C++14	100 / 100	682 ms	19220 KiB

examination

#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ost = tree<T, null_type, greater_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef int64_t lld;
typedef pair<int,int> pii;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define jizz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
template<typename Iter>
ostream& _out(ostream &s, Iter b, Iter e) {
	s<<"[";
	for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
	s<<"]";
	return s;
}
template<class T1,class T2>
ostream& operator<<(ostream& out, pair<T1,T2> p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template< class T, std::size_t N >
ostream& operator<<(ostream& out, array<T,N> c) {
	return _out(out, c.begin(), c.end());
}
template<class T1,class T2>
istream& operator>>(istream& in, pair<T1,T2>& p) {
	return in >> p.ff >> p.ss;
}
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) {
	return _out(s,c.begin(),c.end());
}

typedef pair<array<int, 3>, pii> P;
vector<P> v;
vector<int> bit, ans, as, bs, cs;
int totalbits = 0;
void update(int i, int x){
	do bit[i] += x;
	while((i+=i&-i) < bit.size());
	totalbits += x;
}
int query(int i){
	int ans = 0;
	for(;i;i-=i&-i)
		ans += bit[i];
	return ans;
}
void CDQ(int l, int r){
	int mid = l+r>>1;
	if(l == r)return;
	CDQ(l, mid); CDQ(mid+1, r);
	//cout << (pii){l, r};// << endl;
	auto midP = v[mid];
	inplace_merge(v.begin()+l, v.begin()+mid+1, v.begin()+r+1, [](P a, P b){ return a.ff[1] == b.ff[1]?a<b:a.ff[1]<b.ff[1]; });
	//_out(cout, v.begin()+l, v.begin()+r+1);
	for(int i = l; i <= r; i++)
		if(v[i].ss.ss <= mid && !v[i].ss.ff)
			update(v[i].ff[2], 1);
		else if(v[i].ss.ss > mid && v[i].ss.ff)
			ans[v[i].ss.ff]+= query(v[i].ff[2]);
	//cout << bit << endl;
	for(int i = l; i <= r; i++)
		if(v[i].ss.ss <= mid && !v[i].ss.ff)update(v[i].ff[2], -1);
}
int main(){//jizz;
	int n, q;
	cin >> n >> q;
	for(int i = 0; i < n; i++){
		int a, b;
		cin >> a >> b;
		v.pb({{-a, -b, -a-b}, {0, 0}});
		as.pb(-a); bs.pb(-b); cs.pb(-a-b);
	}
	for(int i = 1; i <= q; i++){
		int a, b, c;
		cin >> a >> b >>c;
		v.pb({{-a, -b, -c}, {i, 0}});
		as.pb(-a); bs.pb(-b); cs.pb(-c);
	}
	sort(all(as)); sort(all(bs)); sort(all(cs)); sort(all(v));
	as.erase(unique(all(as)), as.end());
	bs.erase(unique(all(bs)), bs.end());
	cs.erase(unique(all(cs)), cs.end());
	for(int i = 0; i < n+q; i++){
		v[i].ff[0] = lower_bound(all(as), v[i].ff[0])-as.begin()+1;
		v[i].ff[1] = lower_bound(all(bs), v[i].ff[1])-bs.begin()+1;
		v[i].ff[2] = lower_bound(all(cs), v[i].ff[2])-cs.begin()+1;
		v[i].ss.ss = i;
	}
	//cout << v << endl;
	ans.resize(q+1); bit.resize(n+q+2);
	//cout << ans << endl;
	CDQ(0, n+q-1);
	for(int i = 1; i <= q; i++)
		cout << ans[i] << " ";
	cout << endl;
	
} 
/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100

*/

Compilation message (stderr)

examination.cpp: In function 'void update(int, int)':
examination.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((i+=i&-i) < bit.size());
        ~~~~~~~~~~^~~~~~~~~~~~
examination.cpp: In function 'void CDQ(int, int)':
examination.cpp:56:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r>>1;
            ~^~
examination.cpp:60:7: warning: variable 'midP' set but not used [-Wunused-but-set-variable]
  auto midP = v[mid];
       ^~~~

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