oj.uz

답안 #444035

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444035 2021-07-13T03:42:57 Z minhcool Examination (JOI19_examination) C++17
20 / 100
 3000 ms 20108 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 = 350;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, q;
 
int uomp[N << 1];
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
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Runtime error 2 ms 460 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 989 ms 19988 KB Output is correct
2 Correct 1004 ms 19928 KB Output is correct
3 Correct 1068 ms 19968 KB Output is correct
4 Correct 553 ms 19044 KB Output is correct
5 Correct 2902 ms 19980 KB Output is correct
6 Correct 1108 ms 19100 KB Output is correct
7 Correct 1907 ms 19968 KB Output is correct
8 Correct 1018 ms 19852 KB Output is correct
9 Correct 1933 ms 19912 KB Output is correct
10 Correct 2596 ms 19768 KB Output is correct
11 Correct 678 ms 19024 KB Output is correct
12 Correct 1458 ms 18736 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 989 ms 19988 KB Output is correct
2 Correct 1004 ms 19928 KB Output is correct
3 Correct 1068 ms 19968 KB Output is correct
4 Correct 553 ms 19044 KB Output is correct
5 Correct 2902 ms 19980 KB Output is correct
6 Correct 1108 ms 19100 KB Output is correct
7 Correct 1907 ms 19968 KB Output is correct
8 Correct 1018 ms 19852 KB Output is correct
9 Correct 1933 ms 19912 KB Output is correct
10 Correct 2596 ms 19768 KB Output is correct
11 Correct 678 ms 19024 KB Output is correct
12 Correct 1458 ms 18736 KB Output is correct
13 Execution timed out 3042 ms 20108 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Runtime error 2 ms 460 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -