oj.uz

Submission #513757

# Submission time Handle Problem Language Result Execution time Memory
513757 2022-01-17T14:19:47 Z fatemetmhr Examination (JOI19_examination) C++17
20 / 100
 880 ms 10936 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();
			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++)
      |                 ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2664 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Incorrect 14 ms 2944 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 10900 KB Output is correct
2 Correct 534 ms 10900 KB Output is correct
3 Correct 595 ms 10896 KB Output is correct
4 Correct 491 ms 10552 KB Output is correct
5 Correct 421 ms 9944 KB Output is correct
6 Correct 191 ms 8620 KB Output is correct
7 Correct 478 ms 10936 KB Output is correct
8 Correct 778 ms 10896 KB Output is correct
9 Correct 556 ms 10896 KB Output is correct
10 Correct 403 ms 9784 KB Output is correct
11 Correct 455 ms 10412 KB Output is correct
12 Correct 64 ms 8196 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 10900 KB Output is correct
2 Correct 534 ms 10900 KB Output is correct
3 Correct 595 ms 10896 KB Output is correct
4 Correct 491 ms 10552 KB Output is correct
5 Correct 421 ms 9944 KB Output is correct
6 Correct 191 ms 8620 KB Output is correct
7 Correct 478 ms 10936 KB Output is correct
8 Correct 778 ms 10896 KB Output is correct
9 Correct 556 ms 10896 KB Output is correct
10 Correct 403 ms 9784 KB Output is correct
11 Correct 455 ms 10412 KB Output is correct
12 Correct 64 ms 8196 KB Output is correct
13 Incorrect 880 ms 10904 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2664 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Incorrect 14 ms 2944 KB Output isn't correct
8 Halted 0 ms 0 KB -