Submission #1006361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006361		AdamGS	Examination (JOI19_examination)	C++17	100 / 100	450 ms	62996 KiB

examination

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
pair<ll,ll>T[LIM];
ll wynik[LIM];
pair<pair<ll,ll>,ll>pyt[LIM];
vector<pair<ll,pair<ll,ll>>>A, B;
vector<ll>skal;
map<ll,ll>mp;
ll tr[20*LIM], N=1, akt=0;
void upd(int v, ll x) {
	v+=N;
	while(v) {
		tr[v]+=x;
		v/=2;
	}
}
ll cnt(int l, int r) {
	if(l>r) return 0;
	l+=N; r+=N;
	ll ans=tr[l];
	if(l!=r) ans+=tr[r];
	while(l/2!=r/2) {
		if(l%2==0) ans+=tr[l+1];
		if(r%2==1) ans+=tr[r-1];
		l/=2; r/=2;
	}
	return ans;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q;
	cin >> n >> q;
	rep(i, n) {
		cin >> T[i].st >> T[i].nd;
		A.pb({-T[i].st, {-1, T[i].nd}});
		B.pb({-T[i].st, {-1, T[i].nd+T[i].st}});
	}
	rep(i, q) {
		cin >> pyt[i].st.st >> pyt[i].st.nd >> pyt[i].nd;
		pyt[i].nd=max(pyt[i].nd, pyt[i].st.st+pyt[i].st.nd);
		A.pb({-max(pyt[i].st.st, pyt[i].nd-pyt[i].st.nd), {i, pyt[i].st.nd}});
		B.pb({-pyt[i].st.st, {i, max(pyt[i].st.nd, pyt[i].nd-pyt[i].st.st)+pyt[i].st.st}});
		B.pb({-max(pyt[i].st.st, pyt[i].nd-pyt[i].st.nd), {i+q, max(pyt[i].st.nd, pyt[i].nd-pyt[i].st.st)+pyt[i].st.st}});
	}
	for(auto i : A) 
		skal.pb(i.nd.nd);
	for(auto i : B)
		skal.pb(i.nd.nd);
	sort(all(skal));
	for(auto i : skal) 
		if(mp.find(i)==mp.end()) mp[i]=akt++;
	while(N<akt) N*=2;
	sort(all(A));
	for(auto i : A) {
		if(i.nd.st==-1) upd(mp[i.nd.nd], 1);
		else wynik[i.nd.st]+=cnt(mp[i.nd.nd], N-1);
	}
	rep(i, 2*N) tr[i]=0;
	sort(all(B));
	for(auto i : B) {
		if(i.nd.st==-1) upd(mp[i.nd.nd], 1);
		else if(i.nd.st<q) wynik[i.nd.st]+=cnt(mp[i.nd.nd], N-1);
		else wynik[i.nd.st-q]-=cnt(mp[i.nd.nd], N-1);
	}
	rep(i, q) cout << wynik[i] << '\n';
}

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