oj.uz

답안 #223111

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223111 2020-04-14T19:20:24 Z AQT Examination (JOI19_examination) C++14
0 / 100
 2219 ms 114860 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

struct node{
	int l, r;
	tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update> st;
};

int N, Q;
pair<int, int> arr[100005];
int ans[100005];
int a[100005], b[100005], c[100005];
pair<int, int> qu[100005];
node seg[400005];
vector<int> cmp;

void build(int l, int r, int idx){
	seg[idx].l = l, seg[idx].r = r;
	if(l == r){
		return;
	}
	int mid = l+r>>1;
	build(l, mid, 2*idx);
	build(mid+1, r, 2*idx+1);
}

void upd(int p, int v, int idx){
	seg[idx].st.insert(v);
	if(seg[idx].l == seg[idx].r){
		return;
	}
	upd(p, v, 2*idx + (p > seg[idx].l + seg[idx].r >> 1));
}

int query(int l, int r, int k, int idx){
	if(seg[idx].l == l && seg[idx].r == r){
		try{
			return seg[idx].st.order_of_key(k-1);
		}
		catch(exception &e){
			return 0;
		}
		//return seg[idx].st.order_of_key(k-1);
	}
	int mid = seg[idx].l + seg[idx].r >> 1;
	if(r <= mid){
		return query(l, r, k, 2*idx);
	}
	else if(l > mid){
		return query(l, r, k, 2*idx+1);
	}
	else{
		return query(l, mid, k, 2*idx) + query(mid+1, r, k, 2*idx+1);
	}
}

bool comp1(pair<int, int> a, pair<int, int> b){
	return a.first+a.second > b.first+b.second;
}

int getidx(int v){
	return lower_bound(cmp.begin(), cmp.end(), v) - cmp.begin() + 1;
}

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> Q;
	for(int i= 1; i<=N; i++){
		cin >> arr[i].first >> arr[i].second;
		cmp.push_back(arr[i].first);
	}
	sort(arr+1, arr+1+N, comp1);
	sort(cmp.begin(), cmp.end());
	cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
	int M = cmp.size();
	for(int q = 1; q<=Q; q++){
		cin >> a[q] >> b[q] >> c[q];		
		qu[q] = {c[q], q};
	}
	build(1, M, 1);
	sort(qu+1, qu+1+N, greater<pair<int, int>>());
	int idx = 1;
	for(int q = 1; q<=Q; q++){
		while(idx <= N && arr[idx].first + arr[idx].second >= qu[q].first){
			upd(getidx(arr[idx].first), arr[idx].second, 1);
			idx++;
		}
		int n = qu[q].second;
		//cout << n << " " << getidx(a[n]) << "\n";
		if(getidx(a[n]) >= M){
			continue;
		}
		ans[n] = query(getidx(a[n]), M, b[n], 1);
	}
	for(int q = 1; q<=Q; q++){
		cout << ans[q] << "\n";
	}
}

Compilation message

examination.cpp: In function 'void build(int, int, int)':
examination.cpp:26:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r>>1;
            ~^~
examination.cpp: In function 'void upd(int, int, int)':
examination.cpp:36:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  upd(p, v, 2*idx + (p > seg[idx].l + seg[idx].r >> 1));
                         ~~~~~~~~~~~^~~~~~~~~~~~
examination.cpp: In function 'int query(int, int, int, int)':
examination.cpp:49:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = seg[idx].l + seg[idx].r >> 1;
            ~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 34816 KB Output is correct
2 Correct 36 ms 34808 KB Output is correct
3 Correct 36 ms 34816 KB Output is correct
4 Incorrect 37 ms 34816 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2219 ms 114860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2219 ms 114860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 34816 KB Output is correct
2 Correct 36 ms 34808 KB Output is correct
3 Correct 36 ms 34816 KB Output is correct
4 Incorrect 37 ms 34816 KB Output isn't correct
5 Halted 0 ms 0 KB -