oj.uz

Submission #444029

# Submission time Handle Problem Language Result Execution time Memory
444029 2021-07-13T03:05:16 Z minhcool Examination (JOI19_examination) C++17
2 / 100
 3000 ms 25220 KB 
#include<bits/stdc++.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 = 400;

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];

void upd(int pos, int val){
	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};
	}
	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
		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;
				int x = que.top().fi;
				if(x < queries[it].fi.fi) break;
				//cout << x << " " << que.size() << "\n";
				in[que.top().se] = 1;
				upd(uomp[students1[que.top().se].se], 1);
				que.pop();
			}
			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 <= min(n, (i + 1) * block - 1); 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] = 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, (i + 1) * block); j++){
			int tmp = students2[j].se;
			//cout << j << " " << tmp << "\n";
			se.insert({students1[tmp].fi, tmp});
		}
	}
	for(int i = 1; i <= q; i++) cout << answer[i] << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

Compilation message

examination.cpp: In function 'void process()':
examination.cpp:66: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]
   66 |  for(int i = 0; i < vc.size(); i++) uomp[vc[i]] = i + 1;
      |                 ~~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 35 ms 1272 KB Output is correct
8 Correct 41 ms 1292 KB Output is correct
9 Correct 35 ms 1260 KB Output is correct
10 Correct 25 ms 940 KB Output is correct
11 Correct 38 ms 1276 KB Output is correct
12 Correct 28 ms 968 KB Output is correct
13 Correct 32 ms 1288 KB Output is correct
14 Correct 32 ms 1228 KB Output is correct
15 Correct 31 ms 1296 KB Output is correct
16 Correct 67 ms 1248 KB Output is correct
17 Correct 25 ms 972 KB Output is correct
18 Correct 9 ms 844 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 24744 KB Output is correct
2 Correct 1040 ms 25220 KB Output is correct
3 Correct 1282 ms 25204 KB Output is correct
4 Correct 544 ms 20792 KB Output is correct
5 Execution timed out 3069 ms 24260 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 24744 KB Output is correct
2 Correct 1040 ms 25220 KB Output is correct
3 Correct 1282 ms 25204 KB Output is correct
4 Correct 544 ms 20792 KB Output is correct
5 Execution timed out 3069 ms 24260 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 35 ms 1272 KB Output is correct
8 Correct 41 ms 1292 KB Output is correct
9 Correct 35 ms 1260 KB Output is correct
10 Correct 25 ms 940 KB Output is correct
11 Correct 38 ms 1276 KB Output is correct
12 Correct 28 ms 968 KB Output is correct
13 Correct 32 ms 1288 KB Output is correct
14 Correct 32 ms 1228 KB Output is correct
15 Correct 31 ms 1296 KB Output is correct
16 Correct 67 ms 1248 KB Output is correct
17 Correct 25 ms 972 KB Output is correct
18 Correct 9 ms 844 KB Output is correct
19 Correct 1102 ms 24744 KB Output is correct
20 Correct 1040 ms 25220 KB Output is correct
21 Correct 1282 ms 25204 KB Output is correct
22 Correct 544 ms 20792 KB Output is correct
23 Execution timed out 3069 ms 24260 KB Time limit exceeded
24 Halted 0 ms 0 KB -