Submission #678371

#	Time	Username	Problem	Language	Result	Execution time	Memory
678371		Just_	Examination (JOI19_examination)	C++17	100 / 100	1161 ms	58832 KiB

examination

#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;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define endl '\n'
void fopn(string name){
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
const long long INF=1e18,mod=998244353;
int n,q;
const int N=1e5+5;
int s[N],t[N],x[N],y[N],z[N],ans[N];
struct BIT{
	ordered_set T[N];
	void update(int i, int v){
		i=N-i-1;
		for(;i<N;i+=(i&-i))
			T[i].insert(v);
	}
	int query(int i, int v){
		int res=0;i=N-i-1;
		for(;i>0;i-=(i&-i))
			res+=((int)T[i].size()-T[i].order_of_key(v));
		return res;
	}
} T;
bool c1(int a, int b){
	return x[a]>x[b];
}
bool c2(int a, int b){
	return s[a]>s[b];
}
vector<int> a,b;
void add(int i){
	int x=lower_bound(all(a),t[i])-a.begin();
	int y=lower_bound(all(b),s[i]+t[i])-b.begin();
	T.update(x,y);
}
void solve(){
	cin>>n>>q;
	vector<int> pa(n);
	for(int i=0;i<n;i++){
		cin>>s[i]>>t[i];
		pa[i]=i;
		a.pb(t[i]);
		b.pb(s[i]+t[i]);
	}
	sort(all(a));
	a.erase(unique(all(a)),a.end());
	sort(all(b));
	b.erase(unique(all(b)),b.end());
	vector<int> pb(q);
	for(int i=0;i<q;i++){
		cin>>x[i]>>y[i]>>z[i];
		pb[i]=i;
	}
	sort(all(pa),c2);
	sort(all(pb),c1);
	int r=0;
	for(auto it: pb){
		while(r<n && s[pa[r]]>=x[it])
			add(pa[r++]);
		int k=lower_bound(all(a),y[it])-a.begin();
		int j=lower_bound(all(b),z[it])-b.begin();
		ans[it]=T.query(k,j);
	}
	for(int i=0;i<q;i++)
		cout<<ans[i]<<'\n';
}
main(){
	//fopn("newbarn");
	//ios;
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}

Compilation message (stderr)

examination.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 | main(){
      | ^~~~
examination.cpp: In function 'void fopn(std::string)':
examination.cpp:15:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:16:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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