Submission #444532

#	Time	Username	Problem	Language	Result	Execution time	Memory
444532		minhcool	Examination (JOI19_examination)	C++17	43 / 100	3064 ms	19288 KiB

examination

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define hash hashy
#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 = 900;
 
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){
	
}
 
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);
}
 
ii que[N];
 
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[i].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, 0)) - 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;
	int cnt_que = 0;
	for(int i = n/block + 2; i >= 0; i--){// l = (i * block), r = (i + 1) * block - 1
		//cout << i << "\n";
		int itr = 0;
		for(set<ii>::iterator it = se.begin(); it != se.end(); it++){
			itr++;
			que[itr] = (*it);
		}
		//stack<ii> que;
		//for(set<ii>::iterator it = se.begin(); it != se.end(); it++) 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);
		vector<ii> vc1;
		for(int j = max(1, i * block); j < min(n + 1, (i + 1) * block); j++){
			int tmp = students2[j].se;
			//if(!tmp) cout << j << " " << tmp << "\n";
			vc1.pb({students1[tmp].fi, tmp});
		}
		sort(vc1.begin(), vc1.end());
		for(auto it : srt[i]){
			//cout << it << " " << i << "\n";
				while(1){
					if(!itr) break;
					ii temp = que[itr];
					//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[students2[j].se].se], -1);
					int pos = uomp[students1[temp.se].se];
					for(; pos <= n + q; pos += pos & -pos) bit[pos]++;
					//upd(uomp[students1[temp.se].se], 1);
					itr--;
				}
			int temp = lower_bound(students2 + 1, students2 + n + 1, make_pair(queries[it].se, 0)) - 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);
					int pos = uomp[students1[students2[j].se].se];
					for(; pos <= n + q; pos += pos & -pos) bit[pos]--;
				}
			} 
			for(int j = temp; j < lst; 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);
					int pos = uomp[students1[students2[j].se].se];
					for(; pos <= n + q; pos += pos & -pos) bit[pos]++;
				}
			}
			lst = temp;
			while(1){
				if(!vc1.size()) break;
				if(vc1.back().fi < queries[it].fi.fi) break;
				int ind = vc1.back().se;
				if(!in[ind] && students1[ind].fi + students1[ind].se >= queries[it].se){
					in[ind] = 1;
					//assert(ind);
					int pos = uomp[students1[ind].se];
					for(; pos <= n + q; pos += pos & -pos) bit[pos]++;
				}
				vc1.pop_back();
				//cout << vc1.size() << "\n";
			}
			answer[it] = get(n + q) - get(uomp[queries[it].fi.se] - 1);
			cnt_que++;
          if((cnt_que * 10 >= q * 9) && !(cnt_que % 10)){
			if((double)clock() / CLOCKS_PER_SEC >= 2.9){
             	return;
			}
          }
		}
		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:20:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   20 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
examination.cpp: In function 'void process()':
examination.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int i = 0; i < vc.size(); i++) uomp[vc[i]] = i + 1;
      |                 ~~^~~~~~~~~~~

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