Submission #963525

#TimeUsernameProblemLanguageResultExecution timeMemory
963525noobcodurExamination (JOI19_examination)C++14
100 / 100
557 ms85120 KiB
#include<bits/stdc++.h>
using namespace std;

using ld = long double;

#define int long long
#define pii pair<int,int>
#define forn(i,j) for(int i = 0; i < j; ++i)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define vi vector<int>
#define vpii vector<pii>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()

const int MOD = 1e9+7; const int INF = 1e17+1; const int maxN = 2e5+1;

void setIO(string name){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	if(!name.empty()){
		freopen((name + ".in").c_str(),"r",stdin);
		freopen((name + ".out").c_str(),"w",stdout);
	}
}

vi st1[4*maxN],st2[4*maxN];
vpii num;

void build(int pos, int l, int r){
	if(l == r){
		st1[pos].pb(num[l].s);
		st2[pos].pb(num[l].f + num[l].s);

		return;
	}

	int mid = (l+r)/2;
	build(2*pos,l,mid);
	build(2*pos+1,mid+1,r);

	merge(all(st1[2*pos]),all(st1[2*pos+1]),back_inserter(st1[pos]));
	merge(all(st2[2*pos]),all(st2[2*pos+1]),back_inserter(st2[pos]));
}

int query1(int pos, int l, int r, int ql, int qr, int x){
	if(l > qr || r < ql){
		return 0;
	}

	if(ql <= l && r <= qr){
		return st1[pos].end() - lower_bound(all(st1[pos]),x);
	}

	int mid = (l+r)/2;

	return query1(2*pos,l,mid,ql,qr,x) + query1(2*pos+1,mid+1,r,ql,qr,x);
}

int query2(int pos, int l, int r, int ql, int qr, int x){
	if(l > qr || r < ql) return 0;

	if(ql <= l && r <= qr){
		return st2[pos].end() - lower_bound(all(st2[pos]),x);
	}

	int mid = (l+r)/2;

	return query2(2*pos,l,mid,ql,qr,x) + query2(2*pos+1,mid+1,r,ql,qr,x);
}

signed main(){
	setIO("");
	int n,q; cin >> n >> q;
	num.resize(n);

	forn(i,n){
		cin >> num[i].f >> num[i].s;
	}

	sort(all(num));

	build(1,0,n-1);

	while(q--){
		int x,y,z; cin >> x >> y >> z;

		int d = z - y;
		int res = 0;
		if(d >= x){
			pii j = {x,0};
			int l = lower_bound(all(num),j) - num.begin();
			j = {d,0};
			int r = lower_bound(all(num),j) - num.begin() - 1;

			res += query2(1,0,n-1,l,r,z);
			x = d;
		}

		pii j = {x,0}; int l = lower_bound(all(num),j) - num.begin();

		res += query1(1,0,n-1,l,n-1,y);

		cout << res << endl;
	}
}

Compilation message (stderr)

examination.cpp: In function 'void setIO(std::string)':
examination.cpp:24:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   freopen((name + ".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   freopen((name + ".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...