Submission #1211253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211253		thelegendary08	Examination (JOI19_examination)	C++17	100 / 100	753 ms	83548 KiB

examination

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
struct Query{
	int x,y,sum;
};
struct segtree{
	int n; 
	vi tree;
	segtree(int x){
		n = x;
		tree.resize(4 * n + 5);
	}
	void update(int k, int x){
		k += n;
		tree[k] = x;
		for(k/=2; k>=1; k/=2){
			tree[k] = tree[k*2] + tree[k*2+1];
		}
	}
	void add(int k, int x){
		k += n;
		tree[k] += x;
		for(k/=2; k>=1; k/=2){
			tree[k] = tree[k*2] + tree[k*2+1];
		}
	}
	int quer(int l, int r){
		if(l > r)return 0;
		l += n; r += n; int ret = 0;
		while(l <= r){
			if(l % 2 == 1)ret += tree[l++];
			if(r % 2 == 0)ret += tree[r--];
			l/=2; r/=2;
		}
		return ret;
	}
};
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin(".in");
	//ofstream cout(".out");
	in2(n,q);
	vpii pts;
	set<int>s;
	f0r(i,n){
		in2(x,y);
		pts.pb(mp(x,y));
		s.insert(x);
	}
	
	vector<Query>quers;
	f0r(i,q){
		in3(a,b,c);
		quers.pb({a,b,c});
		s.insert(a);
	}
	
	
	vector<pair<pair<int,pii>,int>> a;
	vector<pair<pair<int,pii>,int>> b;
	f0r(i, q){
		a.pb(mp(mp(quers[i].sum, mp(quers[i].x, quers[i].sum - quers[i].y)),i));
		b.pb(mp(mp(quers[i].y, mp(max(quers[i].sum - quers[i].y + 1, quers[i].x), 4e18)),i));
		// pout(a[i].first.second);
		// pout(b[i].first.second);
		s.insert(quers[i].x);
		s.insert(quers[i].sum - quers[i].y);
		s.insert(max(quers[i].sum - quers[i].y + 1, quers[i].x));
	}
	s.insert(4e18);
	sort(rall(a)); sort(rall(b));
	
	
	mii compress;
	int cnt = 0;
	for(auto u : s){
		// cout<<u<<' ';
		compress[u] = cnt;
		cnt++;
	}
	// cout<<'\n';
	int sz = s.size();
	segtree sumtree = segtree(sz);
	segtree ytree = segtree(sz);
	
	
	vpii sy;
	f0r(i,n){
		sy.pb(mp(pts[i].second, pts[i].first));
	}
	sort(rall(sy));
	
	vpii ssum;
	f0r(i, n){
		ssum.pb(mp(pts[i].first + pts[i].second, pts[i].first));
	}
	sort(rall(ssum));
	
	vi ans(q);
	int ptr = 0;
	f0r(i, q){
		while(ptr < n && sy[ptr].first >= b[i].first.first){
			ytree.add(compress[sy[ptr].second], 1);
			ptr++;
		}
		ans[b[i].second] += ytree.quer(compress[b[i].first.second.first], compress[b[i].first.second.second]);
	}
	
	ptr = 0;
	f0r(i, q){
		while(ptr < n && ssum[ptr].first >= a[i].first.first){
			sumtree.add(compress[ssum[ptr].second], 1);
			ptr++;
		}
		ans[a[i].second] += sumtree.quer(compress[a[i].first.second.first], compress[a[i].first.second.second]);
	}
	
	f0r(i, q){
		out(ans[i]);
	}
	
	
}

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