oj.uz

Submission #766010

# Submission time Handle Problem Language Result Execution time Memory
766010 2023-06-25T08:44:34 Z minhcool Examination (JOI19_examination) C++17
0 / 100
 612 ms 106920 KB 
#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int n, s[N], t[N];
vector<ii> students;
vector<iiii> queries;

int answer[N];

bool cmp(ii a, ii b){
	return (a.fi + a.se < b.fi + b.se);
}

bool cmp2(iiii a, iiii b){
	return (a.se.fi > b.se.fi);
}

vector<int> diffnum[N << 2];
vector<int> bit[N << 2];

vector<ii> diffx;
vector<int> diffy;

void upd(int id, int id2, int val){
	for(; id2 < bit[id].size(); id2 += id2 & -id2) bit[id][id2] += val;
}

int get(int id, int id2){
	int ans = 0;
	for(; id2; id2 -= id2 & -id2) ans += bit[id][id2];
	return ans;
}

void build(int id, int l, int r){
	for(int i = l; i <= r; i++) diffnum[id].pb(t[diffx[i].se]);
	diffnum[id].pb(-1);
	sort(diffnum[id].begin(), diffnum[id].end());
	diffnum[id].resize(unique(diffnum[id].begin(), diffnum[id].end()) - diffnum[id].begin());
	bit[id].resize(diffnum[id].size());
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
}

void upd(int id, int l, int r, int pos, int x){
//	cout << "UPD " << l << " " << r << " " << pos << " " << x << "\n";
	int temp = lower_bound(diffnum[id].begin(), diffnum[id].end(), x) - diffnum[id].begin();
	upd(id, temp, 1);
	if(l == r) return;
	int mid = (l + r) >> 1;
	if(pos <= mid) upd(id << 1, l, mid, pos, x);
	else upd(id << 1 | 1, mid + 1, r, pos, x);
}

int cal(int id, int l, int r, int L, int R, int mini){
	if(l > R || r < L) return 0;
	if(l >= L && r <= R){
		int temp = lower_bound(diffnum[id].begin(), diffnum[id].end(), mini) - diffnum[id].begin();
		temp--;
	//	cout << id << " ";
	//	for(auto it : diffnum[id]) cout << it << " ";
	//	cout << l << " " << r << " " << mini << " "<< temp << "\n";
		return get(id, bit[id].size() - 1) - get(id, temp);
	}
	int mid = (l + r) >> 1;
	return cal(id << 1, l, mid, L, R, mini) + cal(id << 1 | 1, mid + 1, r, L, R, mini);
}

#ifdef local
void process(){
	int q;
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> s[i] >> t[i];
		diffx.pb({s[i], i});
		//diffy.pb(t[i]);
		students.pb({s[i], t[i]});
	}
	diffx.pb({-1, -1});
	sort(diffx.begin(), diffx.end());
	//sort(diffy.begin(), diffy.end());
	//diffx.resize(unique(diffx.begin(), diffx.end()) - diffx.begin());
	//diffy.resize(unique(diffy.begin(), diffy.end()) - diffy.begin());
	build(1, 1, diffx.size() - 1);
	sort(students.begin(), students.end(), cmp);
	for(int i = 1; i <= q; i++){
		int x, y, z;
		cin >> x >> y >> z;
		queries.pb({{x, y}, {z, i}});
	}
	sort(queries.begin(), queries.end(), cmp2);
	for(auto it : queries){
		while(students.size() && (students.back().fi + students.back().se) >= it.se.fi){
			int temp = lower_bound(diffx.begin(), diffx.end(), make_pair(students.back().fi, -oo)) - diffx.begin();
			upd(1, 1, diffx.size() - 1, temp, students.back().se);
		//	cout << students.back().fi << " " << students.back().se << "\n";
			students.pop_back();
		}
		int temp1 = lower_bound(diffx.begin(), diffx.end(), make_pair(it.fi.fi, -oo)) - diffx.begin();
		//cout << "LB " << temp1 << "\n";
	//	cout << temp1 << "\n";
		answer[it.se.se] = cal(1, 1, diffx.size() - 1, temp1, diffx.size() - 1, it.fi.se); 
	}
	for(int i = 1; i <= q; i++) cout << answer[i] << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

Compilation message

examination.cpp: In function 'void upd(long long int, long long int, long long int)':
examination.cpp:52:12: 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]
   52 |  for(; id2 < bit[id].size(); id2 += id2 & -id2) bit[id][id2] += val;
      |        ~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56660 KB Output is correct
2 Correct 24 ms 56704 KB Output is correct
3 Correct 24 ms 56676 KB Output is correct
4 Correct 24 ms 56640 KB Output is correct
5 Correct 24 ms 56672 KB Output is correct
6 Correct 24 ms 56696 KB Output is correct
7 Correct 38 ms 58136 KB Output is correct
8 Correct 33 ms 58192 KB Output is correct
9 Correct 33 ms 58204 KB Output is correct
10 Correct 30 ms 57940 KB Output is correct
11 Incorrect 31 ms 58060 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 612 ms 106920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 612 ms 106920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56660 KB Output is correct
2 Correct 24 ms 56704 KB Output is correct
3 Correct 24 ms 56676 KB Output is correct
4 Correct 24 ms 56640 KB Output is correct
5 Correct 24 ms 56672 KB Output is correct
6 Correct 24 ms 56696 KB Output is correct
7 Correct 38 ms 58136 KB Output is correct
8 Correct 33 ms 58192 KB Output is correct
9 Correct 33 ms 58204 KB Output is correct
10 Correct 30 ms 57940 KB Output is correct
11 Incorrect 31 ms 58060 KB Output isn't correct
12 Halted 0 ms 0 KB -