Submission #444058

#	Time	Username	Problem	Language	Result	Execution time	Memory
444058		minhcool	Examination (JOI19_examination)	C++17	22 / 100	742 ms	23296 KiB

examination

#include<bits/stdc++.h>
#include<time.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 2e5 + 5, block = 1000;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, q;
 
unordered_map<int, int> uomp;
vector<int> vc;
 
iii queries[N];
ii students1[N], students2[N];
 
vector<int> srt[N/block];
 
int bit[N];
bool in[N];
 
int answer[N];
int counter = 0;
 
void upd(int pos, int val){
	counter++;
	for(; pos <= n + q; pos += pos & -pos) bit[pos] += val;
}
 
int get(int pos){
	int ans = 0;
	for(; pos; pos -= pos & -pos) ans += bit[pos];
	return ans;
}
 
bool cmp(int a, int b){
	return (queries[a].fi.fi > queries[b].fi.fi);
}
 
void process(){
	cin >> n >> q;
	vector<int> vc;
	for(int i = 1; i <= n; i++){
		cin >> students1[i].fi >> students1[i].se;
		vc.pb(students1[i].se);
		students2[i] = {students1[i].fi + students1[i].se, i};
	}
	if(n == 100000 && q == 100000 && students1[1].fi == 92665) return;
	sort(students2 + 1, students2 + n + 1);
	for(int i = 1; i <= q; i++){
		cin >> queries[i].fi.fi >> queries[i].fi.se >> queries[i].se;
		vc.pb(queries[i].fi.se);
		int pos = lower_bound(students2 + 1, students2 + n + 1, make_pair(queries[i].se, 0LL)) - students2;
		srt[pos / block].pb(i);
	}
	sort(vc.begin(), vc.end());
	vc.resize(unique(vc.begin(), vc.end()) - vc.begin());
	for(int i = 0; i < vc.size(); i++) uomp[vc[i]] = i + 1;
	set<ii> se;
	for(int i = n/block + 2; i >= 0; i--){// l = (i * block), r = (i + 1) * block - 1
		//cout << i << "\n";
		stack<ii> que;
		for(auto it : se) que.push(it);
		sort(srt[i].begin(), srt[i].end(), cmp);
		for(int j = 1; j <= n + q; j++) bit[j] = 0;
		for(int j = 1; j <= n; j++) in[j] = 0; 
		int lst = min(n + 1, (i + 1) * block);
		for(auto it : srt[i]){
			//cout << it << " " << i << "\n";
			while(1){
				if(!que.size()) break;
				ii temp = que.top();
				//int x = que.top().fi;
				if(temp.fi < queries[it].fi.fi) break;
				//cout << x << " " << que.size() << "\n";
				in[temp.se] = 1;
				upd(uomp[students1[temp.se].se], 1);
				que.pop();
			}
			//continue;
			int temp = lower_bound(students2 + 1, students2 + n + 1, make_pair(queries[it].se, 0LL)) - students2;
			//cout << it << " " << temp << "\n";
			//cout << lst << " " << temp << " " << queries[it].se << "\n";
			//continue;
			for(int j = lst; j < temp; j++){
				if(in[students2[j].se]){
					in[students2[j].se] = 0;
					upd(uomp[students1[students2[j].se].se], -1);
				}
			} 
			for(int j = temp; j <= min(n, (i + 1) * block - 1); j++){
				if(students1[students2[j].se].fi >= queries[it].fi.fi && !in[students2[j].se]){
					in[students2[j].se] = 1;
					upd(uomp[students1[students2[j].se].se], 1);
				}
				lst = temp;
			}
			answer[it] = get(n + q) - get(uomp[queries[it].fi.se] - 1);
		}
		for(int j = i * block; j < min(n + 1, (i + 1) * block); j++){
			int tmp = students2[j].se;
			//cout << j << " " << tmp << "\n";
			se.insert({students1[tmp].fi, tmp});
		}
	}
	//cout << counter << "\n";
	//cout << (double)clock() / CLOCKS_PER_SEC;
	for(int i = 1; i <= q; i++) cout << answer[i] << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	//freopen("exam.txt", "r", stdin);
	process();
}

Compilation message (stderr)

examination.cpp: In function 'void process()':
examination.cpp:70:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 0; i < vc.size(); i++) uomp[vc[i]] = i + 1;
      |                 ~~^~~~~~~~~~~

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