제출 #839422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
839422		daoquanglinh2007	Examination (JOI19_examination)	C++17	100 / 100	2954 ms	89720 KiB

examination

#pragma GCC optimize("Ofast")
#pragma GCC target("sse4")

#include <bits/stdc++.h>
using namespace std;

#define getbit(x, i) ((x&(1<<(i))) != 0)

const int NM = 3e5, SZ = 550, LOG = 18;

struct node{
	mutable int cnt, nxt[2];
	node(int a, int b, int c){
		cnt = a, nxt[0] = b, nxt[1] = c;
	}
};

struct trie{
	vector <node> T;
	void add_node(){
		T.push_back(node(0, -1, -1));
	}
	void init(){
		T.clear();
		add_node();
	}
	void add_int(int x){
		int cur = 0;
		for (int i = LOG; i >= 0; i--){
			T[cur].cnt++;
			int k = getbit(x, i);
			if (T[cur].nxt[k] == -1){
				add_node();
				T[cur].nxt[k] = T.size()-1;
			}
			cur = T[cur].nxt[k];
		}
		T[cur].cnt++;
	}
	int get(int x){
		int cur = 0, res = 0;
		for (int i = LOG; i >= 0; i--){
			int k = getbit(x, i);
			if (k == 0){
				if (T[cur].nxt[1] != -1) res += T[T[cur].nxt[1]].cnt;
			}
			if (T[cur].nxt[k] == -1) return res;
			cur = T[cur].nxt[k];
		}
		res += T[cur].cnt;
		return res;
	}
};

int N, Q;
int S[NM+5], T[NM+5], sum[NM+5], X[NM+5], Y[NM+5], Z[NM+5];
map <int, bool> mark;
vector <int> sorted_arr, id1, id2;
int ans[NM+5];
trie T1[NM+5], T2[SZ+5];

int get(int x){
	if (sorted_arr.back() < x) return -1;
	return lower_bound(sorted_arr.begin(), sorted_arr.end(), x)-sorted_arr.begin();
}

bool cmp1(int x, int y){
	return S[x] > S[y];
}

bool cmp2(int x, int y){
	return X[x] > X[y];
}

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 >> S[i] >> T[i];
		if (!mark[S[i]]){
			sorted_arr.push_back(S[i]);
			mark[S[i]] = 1;
		}
		if (!mark[T[i]]){
			sorted_arr.push_back(T[i]);
			mark[T[i]] = 1;
		}
		sum[i] = S[i]+T[i];
		if (!mark[sum[i]]){
			sorted_arr.push_back(sum[i]);
			mark[sum[i]] = 1;
		}
		id1.push_back(i);
	}
	sort(sorted_arr.begin(), sorted_arr.end());
	for (int i = 1; i <= N; i++){
		S[i] = lower_bound(sorted_arr.begin(), sorted_arr.end(), S[i])-sorted_arr.begin();
		T[i] = lower_bound(sorted_arr.begin(), sorted_arr.end(), T[i])-sorted_arr.begin();
		sum[i] = lower_bound(sorted_arr.begin(), sorted_arr.end(), sum[i])-sorted_arr.begin();
	}
	for (int i = 1; i <= Q; i++){
		cin >> X[i] >> Y[i] >> Z[i];
		X[i] = get(X[i]);
		Y[i] = get(Y[i]);
		Z[i] = get(Z[i]);
		if (X[i] == -1 || Y[i] == -1 || Z[i] == -1){
			ans[i] = 0;
		}
		else{
			id2.push_back(i);
		}
	}
	for (int i = 0; i < sorted_arr.size(); i++)
		T1[i].init();
	for (int i = 0; i < SZ; i++)
		T2[i].init();
	sort(id1.begin(), id1.end(), cmp1);
	sort(id2.begin(), id2.end(), cmp2);
	
	int jj = 0;
	for (int ii = 0; ii < id2.size(); ii++){
		int i = id2[ii];
		while (jj < id1.size()){
			int j = id1[jj];
			if (S[j] < X[i]) break;
			T1[T[j]].add_int(sum[j]);
			T2[T[j]/SZ].add_int(sum[j]);
			jj++;
		}
		ans[i] = 0;
		int L = (Y[i]+SZ-1)/SZ;
		for (int k = L; k < SZ; k++)
			ans[i] += T2[k].get(Z[i]);
		for (int k = Y[i]; k < min((int)sorted_arr.size(), L*SZ); k++)
			ans[i] += T1[k].get(Z[i]);
	}
	for (int i = 1; i <= Q; i++) cout << ans[i] << '\n';
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'int main()':
examination.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for (int i = 0; i < sorted_arr.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~~
examination.cpp:123:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |  for (int ii = 0; ii < id2.size(); ii++){
      |                   ~~~^~~~~~~~~~~~
examination.cpp:125:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   while (jj < id1.size()){
      |          ~~~^~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57