제출 #375272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375272		casperwang	Examination (JOI19_examination)	C++14	100 / 100	673 ms	24388 KiB

examination

#include <bits/stdc++.h>
#define pb emplace_back
#define All(x) x.begin(), x.end()
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

struct node {
	int a, b, c, id;
	node(int _a, int _b, int _c, int i) {
		a = _a, b = _b, c = _c, id = i;
	}
};

const int MAXN = 100000;
int N, Q;
int a, b, c;
vector <node> qry;
vector <int> cpy;
int ans[MAXN];

class Bit {
	private:
		int arr[MAXN*6+1];
		inline int lb(int a) {
			return a &- a;
		}
	public:
		void mdy(int a, int k) {
			for (int i = a; i <= MAXN*6+1; i+=lb(i))
				arr[i] += k;
		}
		int qry(int a) {
			int s = 0;
			for (int i = a; i; i-=lb(i))
				s += arr[i];
			return s;
		}
} bit;

void solve(vector <node> arr) {
	int len = arr.size();
	vector <node> L, R;
	for (int i = 0; i < len/2; i++)
		L.pb(arr[i]);
	for (int i = len/2; i < len; i++)
		R.pb(arr[i]);
	if (L.size() > 1) solve(L);
	if (R.size() > 1) solve(R);
	sort(All(L), [](const node x, const node y) {
		return x.b > y.b;
	});
	sort(All(R), [](const node x, const node y) {
		return x.b > y.b;
	});
	int nowL = 0, nowR = 0, cnt = 0;
	vector <int> del;
	while (nowR < R.size()) {
		int v = nowL < L.size() ? L[nowL].b : 0;
		while (nowR < R.size() && R[nowR].b > v) {
			if (R[nowR].id >= 0) {
				ans[R[nowR].id] += cnt - bit.qry(R[nowR].c-1);
			}
			nowR++;
		}
		while (nowL < L.size() && L[nowL].b == v) {
			if (L[nowL].id == -1) {
				del.pb(L[nowL].c);
				bit.mdy(L[nowL].c, 1);
				cnt++;
			}
			nowL++;
		}
	}
	for (int i : del)
		bit.mdy(i, -1);
	return;
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> Q;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		qry.pb(a, b, a+b, -1);
		cpy.pb(a);
		cpy.pb(b);
		cpy.pb(a+b);
	}
	for (int i = 0; i < Q; i++) {
		cin >> a >> b >> c;
		qry.pb(a, b, c, i);
		cpy.pb(a);
		cpy.pb(b);
		cpy.pb(c);
	}
	sort(All(cpy));
	for (int i = 0; i < N+Q; i++) {
		auto &[a, b, c, _] = qry[i];
		a = lower_bound(All(cpy), a) - cpy.begin() + 1;
		b = lower_bound(All(cpy), b) - cpy.begin() + 1;
		c = lower_bound(All(cpy), c) - cpy.begin() + 1;
	}
	sort(All(qry), [](const node x, const node y){
		if (x.a != y.a) return x.a > y.a;
		if (x.b != y.b) return x.b > y.b;
		if (x.c != y.c) return x.c > y.c;
		return x.id < y.id;
	});
	solve(qry);
	for (int i = 0; i < Q; i++)
		cout << ans[i] << '\n';
}

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

examination.cpp: In function 'void solve(std::vector<node>)':
examination.cpp:60:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  while (nowR < R.size()) {
      |         ~~~~~^~~~~~~~~~
examination.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   int v = nowL < L.size() ? L[nowL].b : 0;
      |           ~~~~~^~~~~~~~~~
examination.cpp:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   while (nowR < R.size() && R[nowR].b > v) {
      |          ~~~~~^~~~~~~~~~
examination.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   while (nowL < L.size() && L[nowL].b == v) {
      |          ~~~~~^~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:101:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |   auto &[a, b, c, _] = qry[i];
      |         ^

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