Submission #667033

#	Time	Username	Problem	Language	Result	Execution time	Memory
667033		Koful123	Examination (JOI19_examination)	C++17	100 / 100	617 ms	67880 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
 
struct Fenwick{
	vector<int> a,fw;
	void upd(int pos,int x){
		int n = fw.size() - 1;
		while(pos <= n){
			fw[pos] += x;
			pos += (pos & -pos);
		}
	}
	int gt(int pos){
		int res = 0;
		while(pos > 0){
			res += fw[pos];
			pos -= (pos & -pos);
		}
		return res;
	}
	int get(int pos){
		return gt(fw.size() - 1) - gt(pos - 1);
	}
};
 
struct SegTree{
	int n; vector<Fenwick> seg; vector<int> arr;
	SegTree(int _n){
		seg.resize(4 * (n = _n) + 4);
		arr.resize(_n + 1);
	};
	void build(int v,int tl,int tr){
		if(tl == tr){
			seg[v].fw.assign(2,0);
			seg[v].a.assign(1,arr[tl]);
			return;
		}
		int tm = (tl + tr) / 2;
		build(v*2,tl,tm), build(v*2+1,tm+1,tr);
		seg[v].fw.resize(seg[v*2].a.size() + seg[v*2+1].a.size() + 1);
		seg[v].a.resize(seg[v*2].a.size() + seg[v*2+1].a.size());
		merge(all(seg[v*2].a),all(seg[v*2+1].a),seg[v].a.begin());
	}
	void upd(int v,int tl,int tr,int pos,int x){
		if(tl > pos || tr < pos) return;
		if(tl == pos && tr == pos){
			seg[v].upd(1,1);
			return;
		}
		int tm = (tl + tr) / 2;
		upd(v*2,tl,tm,pos,x),upd(v*2+1,tm+1,tr,pos,x);
		int co = lower_bound(all(seg[v].a),x) - seg[v].a.begin() + 1;
		seg[v].upd(co,1);
	}
	void upd(int pos,int x){
		upd(1,1,n,pos,x);
	}
	int get(int v,int tl,int tr,int l,int r,int x){
		if(tl > r || tr < l) return 0;
		if(tl >= l && tr <= r){
			int pos = lower_bound(all(seg[v].a),x) - seg[v].a.begin() + 1;
			return seg[v].get(pos);
		}
		int tm = (tl + tr) / 2;
		return get(v*2,tl,tm,l,r,x) + get(v*2+1,tm+1,tr,l,r,x);
	}
	int get(int pos,int x){
		return get(1,1,n,pos,n,x);
	}
};
 
void solve(){
 
	int n,t;
	cin >> n >> t;
 
	vector<int> nums,ans(t + 1); vector<array<int,3>> v(n);
	for(auto &[x,y,z] : v){
		cin >> x >> y; nums.pb(y);
	} 

	sort(all(v),[&](array<int,3> a,array<int,3> b){
		return a[1] < b[1];
	});
	int pos = 0;
	for(auto &[x,y,z] : v){
		z = ++pos;
	}
 	
	vector<array<int,4>> q(t); pos = 0;
	for(auto &[x,y,z,t] : q){
		cin >> x >> y >> z; t = ++pos;
	}

	pos = -1; SegTree seg(n);
	for(int i = 1; i <= n; i++){
		seg.arr[i] = v[i-1][0] + v[i-1][1];
	}

	seg.build(1,1,n);
	sort(all(nums)), sort(rall(v)), sort(rall(q));
	auto f = [&](int x){
		return lower_bound(all(nums),x) - nums.begin() + 1; 
	};

	for(auto[x,y,z,t] : q){
		while(pos + 1 < n && v[pos+1][0] >= x){
			++pos; seg.upd(v[pos][2],v[pos][0] + v[pos][1]); 
		}
		ans[t] = seg.get(f(y),z); 
	}
 
	for(int i = 1; i <= t; i++	){
		cout << ans[i] << endl;
	}
}
 
signed main(){	
 		
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int t = 1;
//	cin >> t;
 
	while(t--)
		solve();
 
	return 0;
}

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