Submission #513761

#	Time	Username	Problem	Language	Result	Execution time	Memory
513761		fatemetmhr	Examination (JOI19_examination)	C++17	100 / 100	1391 ms	10948 KiB

examination

//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const int ssq   =  330;
const ll  inf   =  2e18;

vector <pair<int, int>> av[maxn5];
int s[maxn5], t[maxn5], a[maxn5];
int b[maxn5], c[maxn5], gr[maxn5];
int st1[maxn5], st2[maxn5], per[maxn5];
int valcmp[maxn5], out[maxn5];
map <int, int> ex;
bool mark[maxn5];

inline bool cmp1(int i, int j){return s[i] < s[j];}
inline bool cmp2(int i, int j){return t[i] < t[j];}
inline bool cmp3(int i, int j){return a[i] < a[j];}

inline void remo(int id){
	mark[id] = true;
	for(int i = 0; i < av[gr[id]].size(); i++) 
		if(av[gr[id]][i].fi <= s[id] + t[id])
			av[gr[id]][i].se--;
	return;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int n, q; cin >> n >> q;
	for(int i = 0; i < n; i++){
		cin >> s[i] >> t[i];
		st1[i] = i;
		st2[i] = i;
	}
	sort(st1, st1 + n, cmp1); // bar hasbe s
	sort(st2, st2 + n, cmp2); // bar hasbe t
	
	for(int i = 0; i < n; i++)
		valcmp[i] = t[st2[i]];
	
	for(int i = 0; i < n; i += ssq){
		ex.clear();
		for(int j = i; j < min(n, i + ssq); j++){
			int u = st2[j];
			gr[u] = i;
			ex[-s[u] - t[u]]++;
		}
		int last = 0;
		for(auto it = ex.begin(); it != ex.end(); it++){
			last += (it -> se);
			av[i].pb({-1 * (it -> fi), last});
		}
		reverse(all(av[i]));
	}
	
	for(int i = 0; i < q; i++){
		cin >> a[i] >> b[i] >> c[i];
		per[i] = i;
	}
	sort(per, per + q, cmp3);
	
	int pt = 0;
	
	for(int i = 0; i < q; i++){
		int v = per[i];
		//cout << "query of " << v << ' ' << a[v] << ' '<< b[v] << ' ' << c[v] << endl;
		while(pt < n && a[v] > s[st1[pt]]){
			remo(st1[pt]);
			pt++;
		}
		int ans = 0;
		int l = lower_bound(valcmp, valcmp + n, b[v]) - valcmp;
		//cout << "hmm " << l << endl;
		while(l < n && l % ssq != 0){
			if(!mark[st2[l]] && s[st2[l]] + t[st2[l]] >= c[v])
				ans++;
			l++;
		}
		//cout << "ok " << ans << endl;
		while(l < n){
			int p = lower_bound(all(av[l]), mp(c[v], -1)) - av[l].begin();
			if(p < av[l].size())
				ans += av[l][p].se;
			l += ssq;
		}
		out[v] = ans;
	}
	for(int i = 0; i < q; i++)
		cout << out[i] << '\n';
}

/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
*/

Compilation message (stderr)

examination.cpp: In function 'void remo(int)':
examination.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0; i < av[gr[id]].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:102:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |    if(p < av[l].size())
      |       ~~^~~~~~~~~~~~~~

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