제출 #640102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640102		ghostwriter	Examination (JOI19_examination)	C++14	100 / 100	661 ms	35728 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    CTL - Da Lat
    Cay ngay cay dem nhung deo duoc cong nhan
*/
struct Student {
	int s, t;
	Student() {}
	Student(int s, int t) : s(s), t(t) {}
};
struct Query {
	int a, b, c, id;
	Query() {}
	Query(int a, int b, int c, int id) : a(a), b(b), c(c), id(id) {}
};
bool cmp(Student &a, Student &b) { return a.s + a.t > b.s + b.t; }
bool cmp1(Query &a, Query &b) { return a.c > b.c; }
const int N = 1e5 + 1;
int n, q, a[N], b[N], ans[N];
Student s[N];
vi f[N], f1[N];
Query query[N];
pi getpos(int a, int b) {
	int pos1, pos2;
	if (a > ::a[n]) pos1 = n + 1;
	else pos1 = lb(::a + 1, ::a + 1 + n, a) - ::a;
	if (b > ::b[n]) pos2 = n + 1;
	else pos2 = lb(::b + 1, ::b + 1 + n, b) - ::b;
	return {pos1, pos2};
}
void preget(int x, int y) { for (int i = x; i <= n; i += (i & -i)) f1[i].pb(y); }
void preupd(int x, int y) { for (int i = x; i >= 1; i -= (i & -i)) f1[i].pb(y); }
void process() {
	for (int i = 1; i <= n; ++i) {
		f1[i].pb(-1);
		sort(all(f1[i]));
		f[i].resize(sz(f1[i]), 0);
	}
}
int get(int x, int y) {
	int rs = 0;
	for (int i = x; i <= n; i += (i & -i)) {
		int m = sz(f[i]);
		for (int j = lb(all(f1[i]), y) - f1[i].begin(); j < m; j += (j & -j)) rs += f[i][j];
	}
	return rs;
}
void upd(int x, int y, int v) {
	for (int i = x; i >= 1; i -= (i & -i))
	for (int j = lb(all(f1[i]), y) - f1[i].begin(); j >= 1; j -= (j & -j))
		f[i][j] += v;
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    cin >> n >> q;
    FOR(i, 1, n) {
    	cin >> s[i].s >> s[i].t;
    	a[i] = s[i].s;
    	b[i] = s[i].t;
    }
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    FOR(i, 1, q) {
    	cin >> query[i].a >> query[i].b >> query[i].c;
    	query[i].id = i;
    }
    FOR(i, 1, q) {
    	int a = query[i].a, b = query[i].b;
    	pi cur = getpos(a, b);
    	preget(cur.st, cur.nd);
    }
    FOR(i, 1, n) {
    	pi cur = getpos(s[i].s, s[i].t);
    	preupd(cur.st, cur.nd);
    }
    process();
    sort(s + 1, s + 1 + n, cmp);
    sort(query + 1, query + 1 + q, cmp1);
    int l = 1;
    FOR(i, 1, q) {
    	int a = query[i].a, b = query[i].b, c = query[i].c, id = query[i].id;
    	pi tmp = getpos(a, b);
    	a = tmp.st;
    	b = tmp.nd;
    	WHILE(l <= n && s[l].s + s[l].t >= c) {
    		pi cur = getpos(s[l].s, s[l].t);
    		upd(cur.st, cur.nd, 1);
    		++l;
    	}
    	ans[id] = get(a, b);
    }
    FOR(i, 1, q) cout << ans[i] << '\n';
    return 0;
}
/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
*/

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

examination.cpp: In function 'int main()':
examination.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
examination.cpp:88:5: note: in expansion of macro 'FOR'
   88 |     FOR(i, 1, n) {
      |     ^~~
examination.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
examination.cpp:95:5: note: in expansion of macro 'FOR'
   95 |     FOR(i, 1, q) {
      |     ^~~
examination.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
examination.cpp:99:5: note: in expansion of macro 'FOR'
   99 |     FOR(i, 1, q) {
      |     ^~~
examination.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
examination.cpp:104:5: note: in expansion of macro 'FOR'
  104 |     FOR(i, 1, n) {
      |     ^~~
examination.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
examination.cpp:112:5: note: in expansion of macro 'FOR'
  112 |     FOR(i, 1, q) {
      |     ^~~
examination.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
examination.cpp:124:5: note: in expansion of macro 'FOR'
  124 |     FOR(i, 1, q) cout << ans[i] << '\n';
      |     ^~~

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