oj.uz

Submission #513761

# Submission time Handle Problem Language Result Execution time Memory
513761 2022-01-17T14:30:36 Z fatemetmhr Examination (JOI19_examination) C++17
100 / 100
 1391 ms 10948 KB 
//  ~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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2664 KB Output is correct
2 Correct 1 ms 2672 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 2 ms 2672 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 11 ms 3060 KB Output is correct
8 Correct 13 ms 3000 KB Output is correct
9 Correct 17 ms 2928 KB Output is correct
10 Correct 12 ms 2936 KB Output is correct
11 Correct 10 ms 3020 KB Output is correct
12 Correct 6 ms 2804 KB Output is correct
13 Correct 11 ms 2936 KB Output is correct
14 Correct 11 ms 3012 KB Output is correct
15 Correct 14 ms 3036 KB Output is correct
16 Correct 9 ms 2968 KB Output is correct
17 Correct 9 ms 3008 KB Output is correct
18 Correct 3 ms 2788 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 9520 KB Output is correct
2 Correct 567 ms 9516 KB Output is correct
3 Correct 550 ms 9544 KB Output is correct
4 Correct 633 ms 9592 KB Output is correct
5 Correct 428 ms 8976 KB Output is correct
6 Correct 197 ms 8484 KB Output is correct
7 Correct 376 ms 9544 KB Output is correct
8 Correct 795 ms 9592 KB Output is correct
9 Correct 717 ms 9596 KB Output is correct
10 Correct 371 ms 8920 KB Output is correct
11 Correct 454 ms 9568 KB Output is correct
12 Correct 75 ms 8108 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 9520 KB Output is correct
2 Correct 567 ms 9516 KB Output is correct
3 Correct 550 ms 9544 KB Output is correct
4 Correct 633 ms 9592 KB Output is correct
5 Correct 428 ms 8976 KB Output is correct
6 Correct 197 ms 8484 KB Output is correct
7 Correct 376 ms 9544 KB Output is correct
8 Correct 795 ms 9592 KB Output is correct
9 Correct 717 ms 9596 KB Output is correct
10 Correct 371 ms 8920 KB Output is correct
11 Correct 454 ms 9568 KB Output is correct
12 Correct 75 ms 8108 KB Output is correct
13 Correct 912 ms 9684 KB Output is correct
14 Correct 786 ms 10896 KB Output is correct
15 Correct 628 ms 10892 KB Output is correct
16 Correct 1055 ms 10904 KB Output is correct
17 Correct 450 ms 10260 KB Output is correct
18 Correct 248 ms 8644 KB Output is correct
19 Correct 907 ms 10896 KB Output is correct
20 Correct 936 ms 10888 KB Output is correct
21 Correct 1071 ms 10896 KB Output is correct
22 Correct 393 ms 9792 KB Output is correct
23 Correct 407 ms 10392 KB Output is correct
24 Correct 89 ms 8188 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2664 KB Output is correct
2 Correct 1 ms 2672 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 2 ms 2672 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 11 ms 3060 KB Output is correct
8 Correct 13 ms 3000 KB Output is correct
9 Correct 17 ms 2928 KB Output is correct
10 Correct 12 ms 2936 KB Output is correct
11 Correct 10 ms 3020 KB Output is correct
12 Correct 6 ms 2804 KB Output is correct
13 Correct 11 ms 2936 KB Output is correct
14 Correct 11 ms 3012 KB Output is correct
15 Correct 14 ms 3036 KB Output is correct
16 Correct 9 ms 2968 KB Output is correct
17 Correct 9 ms 3008 KB Output is correct
18 Correct 3 ms 2788 KB Output is correct
19 Correct 544 ms 9520 KB Output is correct
20 Correct 567 ms 9516 KB Output is correct
21 Correct 550 ms 9544 KB Output is correct
22 Correct 633 ms 9592 KB Output is correct
23 Correct 428 ms 8976 KB Output is correct
24 Correct 197 ms 8484 KB Output is correct
25 Correct 376 ms 9544 KB Output is correct
26 Correct 795 ms 9592 KB Output is correct
27 Correct 717 ms 9596 KB Output is correct
28 Correct 371 ms 8920 KB Output is correct
29 Correct 454 ms 9568 KB Output is correct
30 Correct 75 ms 8108 KB Output is correct
31 Correct 912 ms 9684 KB Output is correct
32 Correct 786 ms 10896 KB Output is correct
33 Correct 628 ms 10892 KB Output is correct
34 Correct 1055 ms 10904 KB Output is correct
35 Correct 450 ms 10260 KB Output is correct
36 Correct 248 ms 8644 KB Output is correct
37 Correct 907 ms 10896 KB Output is correct
38 Correct 936 ms 10888 KB Output is correct
39 Correct 1071 ms 10896 KB Output is correct
40 Correct 393 ms 9792 KB Output is correct
41 Correct 407 ms 10392 KB Output is correct
42 Correct 89 ms 8188 KB Output is correct
43 Correct 987 ms 10888 KB Output is correct
44 Correct 989 ms 10896 KB Output is correct
45 Correct 795 ms 10948 KB Output is correct
46 Correct 1071 ms 10892 KB Output is correct
47 Correct 516 ms 10904 KB Output is correct
48 Correct 234 ms 8580 KB Output is correct
49 Correct 689 ms 10940 KB Output is correct
50 Correct 1391 ms 10896 KB Output is correct
51 Correct 1136 ms 10900 KB Output is correct
52 Correct 485 ms 10696 KB Output is correct
53 Correct 449 ms 10768 KB Output is correct