oj.uz

Submission #260029

# Submission time Handle Problem Language Result Execution time Memory
260029 2020-08-09T03:37:23 Z minhcool Examination (JOI19_examination) C++17
0 / 100
 2 ms 416 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define ins insert
#define er erase

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

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

const int N = 1e5 + 5;

int n, q, BIT[N], ans[N];
iii queries[N];
ii students[N];

void update(int u){
	for(; u <= 100001 && u; u += (u & -u)){
		//cout << u << " " << u + (u & -u) << "\n";
		++BIT[u];
	}
}

int get(int u){
	if(u < 0) return 0;
	int sum = 0;
	for(; u; u -= (u & -u)) sum += BIT[u];
	return sum;
}

bool cmp(iii a, iii b){
	if(a.fi != b.fi) return a.fi > b.fi;
	return 0;
}

signed main(){
	ios_base::sync_with_stdio(0);
	freopen("examination_19.inp", "r", stdin);
	freopen("examination_19.out", "w", stdout);
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> students[i].fi >> students[i].se;
		++students[i].fi;
		++students[i].se;
	}
	sort(students + 1, students + n + 1, greater<ii>());
	if(n <= 3000 && q <= 3000){
		while(q--){
			int x, y, z, ans = 0;
			cin >> x >> y >> z;
			++x;
			++y;
			z += 2;
			for(int i = 1; i <= n; i++) ans += (x <= students[i].fi && y <= students[i].se && z <= (students[i].fi + students[i].se));
			cout << ans << "\n";
		}
	}
	else{
		for(int i = 1; i <= q; i++){
			//cout << i << "\n";
			int z;
			cin >> queries[i].fi.fi >> queries[i].fi.se >> z;
			++queries[i].fi.fi;
			++queries[i].fi.se;
			queries[i].se = i;
		}
		sort(queries + 1, queries + q + 1, cmp);
		int itr = 1;
		for(int i = 1; i <= q; i++){
			//cout << i << "\n";
			while(itr <= n && students[itr].fi >= queries[i].fi.fi){
				update(students[itr].se);
				++itr;
				//cout << itr << "\n";
			}
			ans[queries[i].se] = get(100002) - get(queries[i].fi.se - 1);
		}
		for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
	}
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:44:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("examination_19.inp", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:45:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("examination_19.out", "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 57.0

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