Submission #629994

#	Time	Username	Problem	Language	Result	Execution time	Memory
629994		Arnch	Examination (JOI19_examination)	C++17	2 / 100	1573 ms	115040 KiB

examination

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define mak make_pair

//constexpr int PRI = 1000696969;
constexpr ll INF = 1e18, N = 1e5 + 10, MOD = 1e9 + 7, SQ = 350;

int n, q; 
int x[N], y[N], sum[N];
int a[N], b[N], c[N];
int fen[SQ][N], cur[N];
int id[N], last[N];
int ans_t[N];

void compress() {
	vector<int> vc;
	for(int i = 0; i < n; i++) {
		vc.push_back(x[i]), vc.push_back(x[i] + y[i]);
	}
	for(int i = 0; i < q; i++) {
		vc.push_back(a[i]), vc.push_back(c[i]);
	}
	sort(All(vc));
	for(int i = 0; i < n; i++) {
		sum[i] = lower_bound(All(vc), x[i] + y[i]) - vc.begin();
		x[i] = lower_bound(All(vc), x[i]) - vc.begin();
	}	
	for(int i = 0; i < q; i++) {
		a[i] = lower_bound(All(vc), a[i]) - vc.begin();
		c[i] = lower_bound(All(vc), c[i]) - vc.begin();
	}

	vector<pair<int, int> > block, b2;
	for(int i = 0; i < n; i++) block.push_back({x[i], i});
	for(int i = 0; i < q; i++) b2.push_back({a[i], i});
	sort(All(block)), sort(All(b2));

	for(int i = n - 1; i >= 0; i--) {
		id[block[i].second] = i;
		while(!b2.empty() && b2.back().first > block[i].first) {
			last[b2.back().first] = i + 1;
			b2.pop_back();
		}
	}
	while(!b2.empty()) {
		last[b2.back().first] = 0;
		b2.pop_back();
	}
}
bool cmp(pair<int, int> i, pair<int, int> j) {
	int cnt1 = 0, cnt2 = 0;
	if(i.second == 0) cnt1 = y[i.first];
	else cnt1 = b[i.first];

	if(j.second == 0) cnt2 = y[j.first];
	else cnt2 = b[j.first];

	if(cnt1 != cnt2) return cnt1 > cnt2;
	return i.second < j.second;
}

void add_fen(int ind, int pos) {
	for(++pos; pos; pos -= (pos & -pos)) 
		fen[ind][pos]++;
}
int get_fen(int ind, int pos) {
	int ans = 0;
	for(++pos; pos < N; pos += (pos & -pos)) 
		ans += fen[ind][pos];
	return ans;
}

void add(int pos, int val) {
	cur[pos] = val;
	add_fen(pos / SQ, val);
}
int solve(int pos, int val) {
	int ans = 0;
	for(int i = pos; i / SQ == pos / SQ; i++) {
		if(cur[i] >= val) ans++;
	}	
	for(int i = pos / SQ + 1; i <= (n - 1) / SQ; i++) {
		ans += get_fen(i, val);
	}
	return ans;
}

int main() {
	ios :: sync_with_stdio(0), cin.tie(0); cout.tie(0);

	cin >>n >>q;
	for(int i = 0; i < n; i++) cin >>x[i] >>y[i];
	for(int i = 0; i < q; i++) cin >>a[i] >>b[i] >>c[i];

	compress();

	vector<pair<int, int> > pos;
	for(int i = 0; i < n; i++) {
		pos.push_back(mak(i, 0));
	}
	for(int i = 0; i < q; i++) {
		pos.push_back(mak(i, 1));
	}
	sort(All(pos), cmp);

	memset(cur, -1, sizeof(cur));
	for(auto j : pos) {
		//cout<<j.first <<' ' <<j.second <<' ';
		//if(j.second == 0) cout<<sum[j.first] <<endl;
		//else cout<<c[j.first] <<endl;

		/*if(j.second == 0) {
			cout<<"^^" <<j.first <<' ' <<id[j.first] <<' ' <<sum[j.first] <<endl;
		} else {
			cout<<"***" <<j.first <<' ' <<last[a[j.first]] <<' ' <<c[j.first] <<endl;
		}*/
	
		if(j.second == 0) {
			add(id[j.first], sum[j.first]);
			continue;
		}
		ans_t[j.first] = solve(last[a[j.first]], c[j.first]);
	}

	for(int j = 0; j < q; j++)
		cout<<ans_t[j] <<endl;

	return 0;
}

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