oj.uz

Submission #157199

# Submission time Handle Problem Language Result Execution time Memory
157199 2019-10-10T03:25:10 Z manh9203 Examination (JOI19_examination) C++17
100 / 100
 2657 ms 257876 KB 
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#pragma GCC optimize("O3")
const int N = 3e5 + 5;
long long n,w,h,q,x[N],y[N],z[N],ans[N],cnt;
pair<long long,long long> stu[N];
pair<pair<int,int>,long long> com[N];
map<long long,int> idx,idy;
vector<long long> dmx,dmy,pos[N],node1[4*N];
vector<int> fen[4*N],point[N],query[N];
vector<pair<long long,int> > node[4*N];
//compress
void build1(int id,int l,int r,int i,int vt){
	if(l>i || r<i){
		return;
	}
	if(l == r){
		node[id].push_back({com[vt].se, vt});
		node1[id].push_back(com[vt].se);
		return;		
	}
	int mid = (l + r) >> 1;
	build1(id<<1, l, mid, i, vt);
	build1(id<<1|1, mid+1, r, i, vt);
	node[id].push_back({com[vt].se, vt});
	node1[id].push_back(com[vt].se);
}

void build(int id,int l,int r){
	if(l == r){
		sort(node[id].begin(), node[id].end());
		sort(node1[id].begin(), node1[id].end());
		for(int i = 0; i < node[id].size(); i++){
			pos[node[id][i].se].push_back(i + 1);
		}
		fen[id].assign(node[id].size() + 5, 0);
		return;
	}
	int mid = (l + r) >> 1;
	build(id<<1, l, mid);
	build(id<<1|1, mid+1, r);
	sort(node[id].begin(), node[id].end());
	sort(node1[id].begin(), node1[id].end());
	for(int i = 0; i < node[id].size(); i++){
		pos[node[id][i].se].push_back(i + 1);
	}
	fen[id].assign(node[id].size() + 5, 0);
}

//upd BIT
void upd(int id,int val,int index){
	for(int i = id; i <= node[index].size(); i += (i&-i)){
		fen[index][i] += val;
	}
}
int get_sum(int id,int index){
	int sum = 0;
	for(int i = id; i >= 1; i -= (i&-i)){
		sum += fen[index][i];
	}
	return sum;
}

//sweep update
void update(int id,int l,int r,int i,int vt){
	if(l>i || r<i){
		return;
	}
	if(l == r){
		cnt++;
		upd(pos[vt][cnt], 1, id);
		return;
	}
	int mid = (l + r) >> 1;
	update(id<<1, l, mid, i, vt);
	update(id<<1|1, mid+1, r, i, vt);
	cnt++;
	upd(pos[vt][cnt], 1, id);
}

//ans query
int get(int id,int l,int r,int i,int j,long long val){
	if(l>j || r<i || i>j){
		return 0;
	}
	if(l>=i && r<=j){
		if(node1[id].size() == 0 || node1[id][node1[id].size()-1] < val){
			return 0;
		}else{
			int dm1 = lower_bound(node1[id].begin(), node1[id].end(), val) - node1[id].begin();
			return get_sum(node1[id].size(), id) - get_sum(dm1, id);
		}
	}
	int mid = (l + r) >> 1;
	return get(id<<1, l, mid, i, j, val) + get(id<<1|1, mid+1, r, i, j, val);
}

//main
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for(int i=1;i<=n;i++){
		cin >> stu[i].fi >> stu[i].se;
		if(idx[stu[i].fi] == 0){
			idx[stu[i].fi] = 1;
			dmx.push_back(stu[i].fi);
		}
		if(idy[stu[i].se] == 0){
			idy[stu[i].se] = 1;
			dmy.push_back(stu[i].se);
		}
	}
	for(int i=1;i<=q;i++){
		cin >> x[i] >> y[i] >> z[i];
		if(idx[x[i]] == 0){
			idx[x[i]] = 1;
			dmx.push_back(x[i]);
		}
		if(idy[y[i]] == 0){
			idy[y[i]] = 1;
			dmy.push_back(y[i]);
		}
	}
	sort(dmx.begin(), dmx.end());
	sort(dmy.begin(), dmy.end());
	w = dmx.size(); h = dmy.size();
	for(int i=0;i<dmx.size();i++){
		idx[dmx[i]] = i+1;
	}
	for(int i=0;i<dmy.size();i++){
		idy[dmy[i]] = i+1;
	}
	for(int i=1;i<=n;i++){
		com[i].fi.fi = idx[stu[i].fi];
		com[i].fi.se = idy[stu[i].se];
		com[i].se = stu[i].fi + stu[i].se;
	}
	for(int i=1;i<=q;i++){
		x[i] = idx[x[i]];
		y[i] = idy[y[i]];
		query[x[i]].push_back(i);
	}
	sort(com+1, com+1+n);
	for(int i=1;i<=n;i++){
		build1(1, 1, h, com[i].fi.se, i);
		point[com[i].fi.fi].push_back(i);
	}
	build(1, 1, h);
	for(int i = w; i >= 1; i--){
		for(int j: point[i]){
			cnt = -1;
			update(1, 1, h, com[j].fi.se, j);
		}
		for(int j: query[i]){
			ans[j] = get(1, 1, h, y[j], h, z[j]);
		}
	}
	for(int i=1;i<=q;i++){
		cout << ans[i] << "\n";
	}
}

Compilation message

examination.cpp: In function 'void build(int, int, int)':
examination.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < node[id].size(); i++){
                  ~~^~~~~~~~~~~~~~~~~
examination.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < node[id].size(); i++){
                 ~~^~~~~~~~~~~~~~~~~
examination.cpp: In function 'void upd(int, int, int)':
examination.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = id; i <= node[index].size(); i += (i&-i)){
                  ~~^~~~~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:129:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<dmx.size();i++){
              ~^~~~~~~~~~~
examination.cpp:132:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<dmy.size();i++){
              ~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 106196 KB Output is correct
2 Correct 102 ms 105976 KB Output is correct
3 Correct 102 ms 106104 KB Output is correct
4 Correct 102 ms 106104 KB Output is correct
5 Correct 102 ms 106104 KB Output is correct
6 Correct 102 ms 106084 KB Output is correct
7 Correct 131 ms 109816 KB Output is correct
8 Correct 133 ms 109788 KB Output is correct
9 Correct 133 ms 109816 KB Output is correct
10 Correct 114 ms 107640 KB Output is correct
11 Correct 124 ms 109196 KB Output is correct
12 Correct 107 ms 107128 KB Output is correct
13 Correct 131 ms 109860 KB Output is correct
14 Correct 143 ms 109856 KB Output is correct
15 Correct 131 ms 109832 KB Output is correct
16 Correct 121 ms 109188 KB Output is correct
17 Correct 112 ms 107152 KB Output is correct
18 Correct 107 ms 106828 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1929 ms 224576 KB Output is correct
2 Correct 1905 ms 224668 KB Output is correct
3 Correct 1857 ms 224624 KB Output is correct
4 Correct 576 ms 144268 KB Output is correct
5 Correct 1226 ms 215396 KB Output is correct
6 Correct 278 ms 135284 KB Output is correct
7 Correct 1740 ms 221932 KB Output is correct
8 Correct 1688 ms 218932 KB Output is correct
9 Correct 1534 ms 216228 KB Output is correct
10 Correct 909 ms 215268 KB Output is correct
11 Correct 466 ms 131392 KB Output is correct
12 Correct 217 ms 126692 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1929 ms 224576 KB Output is correct
2 Correct 1905 ms 224668 KB Output is correct
3 Correct 1857 ms 224624 KB Output is correct
4 Correct 576 ms 144268 KB Output is correct
5 Correct 1226 ms 215396 KB Output is correct
6 Correct 278 ms 135284 KB Output is correct
7 Correct 1740 ms 221932 KB Output is correct
8 Correct 1688 ms 218932 KB Output is correct
9 Correct 1534 ms 216228 KB Output is correct
10 Correct 909 ms 215268 KB Output is correct
11 Correct 466 ms 131392 KB Output is correct
12 Correct 217 ms 126692 KB Output is correct
13 Correct 1911 ms 224888 KB Output is correct
14 Correct 1947 ms 224712 KB Output is correct
15 Correct 1811 ms 224772 KB Output is correct
16 Correct 606 ms 144304 KB Output is correct
17 Correct 1317 ms 215432 KB Output is correct
18 Correct 282 ms 135392 KB Output is correct
19 Correct 1858 ms 224672 KB Output is correct
20 Correct 1900 ms 224568 KB Output is correct
21 Correct 1792 ms 222688 KB Output is correct
22 Correct 915 ms 215148 KB Output is correct
23 Correct 527 ms 131552 KB Output is correct
24 Correct 219 ms 126732 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 106196 KB Output is correct
2 Correct 102 ms 105976 KB Output is correct
3 Correct 102 ms 106104 KB Output is correct
4 Correct 102 ms 106104 KB Output is correct
5 Correct 102 ms 106104 KB Output is correct
6 Correct 102 ms 106084 KB Output is correct
7 Correct 131 ms 109816 KB Output is correct
8 Correct 133 ms 109788 KB Output is correct
9 Correct 133 ms 109816 KB Output is correct
10 Correct 114 ms 107640 KB Output is correct
11 Correct 124 ms 109196 KB Output is correct
12 Correct 107 ms 107128 KB Output is correct
13 Correct 131 ms 109860 KB Output is correct
14 Correct 143 ms 109856 KB Output is correct
15 Correct 131 ms 109832 KB Output is correct
16 Correct 121 ms 109188 KB Output is correct
17 Correct 112 ms 107152 KB Output is correct
18 Correct 107 ms 106828 KB Output is correct
19 Correct 1929 ms 224576 KB Output is correct
20 Correct 1905 ms 224668 KB Output is correct
21 Correct 1857 ms 224624 KB Output is correct
22 Correct 576 ms 144268 KB Output is correct
23 Correct 1226 ms 215396 KB Output is correct
24 Correct 278 ms 135284 KB Output is correct
25 Correct 1740 ms 221932 KB Output is correct
26 Correct 1688 ms 218932 KB Output is correct
27 Correct 1534 ms 216228 KB Output is correct
28 Correct 909 ms 215268 KB Output is correct
29 Correct 466 ms 131392 KB Output is correct
30 Correct 217 ms 126692 KB Output is correct
31 Correct 1911 ms 224888 KB Output is correct
32 Correct 1947 ms 224712 KB Output is correct
33 Correct 1811 ms 224772 KB Output is correct
34 Correct 606 ms 144304 KB Output is correct
35 Correct 1317 ms 215432 KB Output is correct
36 Correct 282 ms 135392 KB Output is correct
37 Correct 1858 ms 224672 KB Output is correct
38 Correct 1900 ms 224568 KB Output is correct
39 Correct 1792 ms 222688 KB Output is correct
40 Correct 915 ms 215148 KB Output is correct
41 Correct 527 ms 131552 KB Output is correct
42 Correct 219 ms 126732 KB Output is correct
43 Correct 2507 ms 257664 KB Output is correct
44 Correct 2494 ms 257876 KB Output is correct
45 Correct 2657 ms 257724 KB Output is correct
46 Correct 791 ms 154852 KB Output is correct
47 Correct 1528 ms 238172 KB Output is correct
48 Correct 282 ms 135180 KB Output is correct
49 Correct 2533 ms 257876 KB Output is correct
50 Correct 2393 ms 257036 KB Output is correct
51 Correct 2344 ms 257072 KB Output is correct
52 Correct 1170 ms 237880 KB Output is correct
53 Correct 606 ms 142180 KB Output is correct