제출 #1281787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281787		KickingKun	Examination (JOI19_examination)	C++20	100 / 100	1502 ms	190636 KiB

examination

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

#define ll long long
#define ull unsigned long long
#define ld long double
#define bigint __int128
#define emb emplace_back
#define pb push_back
#define pii pair <int, int>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define Task ""

#define MASK(k) (1ull << k)
#define bitcnt(k) __builtin_popcount(k)
#define testBit(n, k) ((n >> k) & 1)
#define flipBit(n, k) (n ^ (1ll << k))
#define offBit(n, k) (n & ~MASK(k))
#define onBit(n, k) (n | (1ll << k))

template <class T> bool minimize(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool maximize(T &a, T b) {if (a < b) {a = b; return true;} return false;}

const int N = 1e5 + 5, inf = 1e9, mod = 1e9 + 7;
const ll INF = 1e18;

int n, q;
struct Student {
	int s, t;
	bool operator < (const Student &other) {
		return s + t > other.s + other.t;
	}
} stu[N];

struct Query {
	int a, b, c, id;
	bool operator < (const Query &other) {
		return c > other.c;
	}
} que[N];

unordered_map <int, int> bit[N];
vector <int> cmpx, cmpy;

void update(int x, int y) {
	for (; x <= cmpx.size(); x += x & -x)
		for (int v = y; v <= cmpy.size(); v += v & -v)
			++bit[x][v];
}

int get(int x, int y) {
	int res = 0;
	for (; x > 0; x -= x & -x)
		for (int v = y; v > 0; v -= v & -v) {
			auto it = bit[x].find(v);
			if (it != bit[x].end()) res += it->se;
		}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	if (fopen(Task".inp", "r")) {
		freopen(Task".inp", "r", stdin);
		freopen(Task".out", "w", stdout);
	}

	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> stu[i].s >> stu[i].t;
	sort (stu + 1, stu + n + 1);

	for (int i = 0; i < q; i++) {
		que[i].id = i;
		cin >> que[i].a >> que[i].b >> que[i].c;
	}
	sort (que, que + q);

	for (int i = 1; i <= n; i++) {
		cmpx.emplace_back(inf - stu[i].s + 1);
		cmpy.emplace_back(inf - stu[i].t + 1);
	}
	sort (all(cmpx)); cmpx.resize(unique(all(cmpx)) - cmpx.begin());
	sort (all(cmpy)); cmpy.resize(unique(all(cmpy)) - cmpy.begin());

	vector <int> ans(q);
	for (int i = 0, cur = 0; i < q; i++) {
		auto [a, b, c, id] = que[i];
		while (cur < n && stu[cur + 1].s + stu[cur + 1].t >= c) {
			++cur;
			int x = upper_bound(all(cmpx), inf - stu[cur].s + 1) - cmpx.begin();
			int y = upper_bound(all(cmpy), inf - stu[cur].t + 1) - cmpy.begin();
			update(x, y);
		}

		a = upper_bound(all(cmpx), inf - a + 1) - cmpx.begin();
		b = upper_bound(all(cmpy), inf - b + 1) - cmpy.begin();
		ans[id] = get(a, b);
	}

	for (int i = 0; i < q; i++)
		cout << ans[i] << '\n';
}

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

examination.cpp: In function 'int main()':
examination.cpp:67:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |                 freopen(Task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:68:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |                 freopen(Task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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