oj.uz

Submission #123678

# Submission time Handle Problem Language Result Execution time Memory
123678 2019-07-02T03:49:36 Z 구재현(#3036) Examination (JOI19_examination) C++14
0 / 100
 452 ms 10264 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
using lint = long long;
using pi = pair<int, int>;

struct pnt{
	int x, y, z, idx;
	bool operator<(const pnt &p)const{
		return make_tuple(x, y, z) < make_tuple(p.x, p.y, p.z);
	}
}a[MAXN];

struct foo{
	int x, y, idx;
	bool operator<(const foo &f)const{
		return pi(x, idx) < pi(f.x, f.idx);
	}
};

struct bit{
	int tree[MAXN];
	void add(int x, int v){
		while(x < MAXN){
			tree[x] += v; 
			x += x & -x;
		}
	}
	int query(int x){
		int ret = 0;
		while(x){
			ret += tree[x];
			x -= x & -x;
		}
		return ret;
	}
}bit;

int n, q, ret[MAXN];

void solve(int s, int e){
	if(s == e) return;
	int m = (s + e) / 2;
	solve(s, m); solve(m + 1, e);
	vector<foo> v; 
	for(int i=s; i<=m; i++){
		if(a[i].idx == -1) v.push_back({a[i].y, a[i].z, -1});
	}
	for(int i=m+1; i<=e; i++){
		if(a[i].idx != -1) v.push_back({a[i].y, a[i].z, a[i].idx});
	}
	sort(v.begin(), v.end());
	for(auto &i : v){
		if(i.idx == -1) bit.add(i.y, 1);
		else ret[i.idx] += bit.query(i.y);
	}
	for(auto &i : v){
		if(i.idx == -1) bit.add(i.y, -1);
	}
}

int main(){
	scanf("%d %d",&n,&q);
	for(int i=0; i<n; i++){
		int x, y; scanf("%d %d",&x,&y);
		a[i] = {-x, -y, -x-y, -1};
	}
	for(int i=0; i<q; i++){
		int x, y, z; scanf("%d %d %d",&x,&y,&z);
		a[i + n] = {-x, -y, -z, i};
	}
	vector<int> vx, vy, vz;
	for(int i=0; i<n; i++){
		vx.push_back(a[i].x); vy.push_back(a[i].y); vz.push_back(a[i].z);
	}
	vx.push_back(-2e9);
	vy.push_back(-2e9);
	vz.push_back(-2e9);
	sort(vx.begin(), vx.end());
	sort(vy.begin(), vy.end());
	sort(vz.begin(), vz.end());
	vx.resize(unique(vx.begin(), vx.end()) - vx.begin());
	vy.resize(unique(vy.begin(), vy.end()) - vy.begin());
	vz.resize(unique(vz.begin(), vz.end()) - vz.begin());
	for(int i=0; i<n; i++){
		a[i].x = lower_bound(vx.begin(), vx.end(), a[i].x) - vx.begin();
		a[i].y = lower_bound(vy.begin(), vy.end(), a[i].y) - vy.begin();
		a[i].z = lower_bound(vz.begin(), vz.end(), a[i].z) - vz.begin();
	}
	for(int i=0; i<q; i++){
		a[i+n].x = upper_bound(vx.begin(), vx.end(), a[i+n].x) - vx.begin() - 1;
		a[i+n].y = upper_bound(vy.begin(), vy.end(), a[i+n].y) - vy.begin() - 1;
		a[i+n].z = upper_bound(vz.begin(), vz.end(), a[i+n].z) - vz.begin() - 1;
	}
	sort(a, a + n + q);
	solve(0, n + q - 1);
	for(int i=0; i<q; i++) printf("%d\n", ret[i]);
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
examination.cpp:65:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d %d",&x,&y);
             ~~~~~^~~~~~~~~~~~~~~
examination.cpp:69:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, z; scanf("%d %d %d",&x,&y,&z);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 13 ms 760 KB Output is correct
8 Correct 13 ms 808 KB Output is correct
9 Correct 13 ms 848 KB Output is correct
10 Incorrect 12 ms 724 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 10208 KB Output is correct
2 Correct 444 ms 10264 KB Output is correct
3 Correct 452 ms 10264 KB Output is correct
4 Correct 376 ms 9556 KB Output is correct
5 Correct 335 ms 9332 KB Output is correct
6 Incorrect 270 ms 8396 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 10208 KB Output is correct
2 Correct 444 ms 10264 KB Output is correct
3 Correct 452 ms 10264 KB Output is correct
4 Correct 376 ms 9556 KB Output is correct
5 Correct 335 ms 9332 KB Output is correct
6 Incorrect 270 ms 8396 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 13 ms 760 KB Output is correct
8 Correct 13 ms 808 KB Output is correct
9 Correct 13 ms 848 KB Output is correct
10 Incorrect 12 ms 724 KB Output isn't correct
11 Halted 0 ms 0 KB -