oj.uz

Submission #640102

# Submission time Handle Problem Language Result Execution time Memory
640102 2022-09-13T15:32:09 Z ghostwriter Examination (JOI19_examination) C++14
100 / 100
 661 ms 35728 KB 
#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
*/

Compilation message

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5036 KB Output is correct
4 Correct 2 ms 5032 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 12 ms 5716 KB Output is correct
8 Correct 11 ms 5756 KB Output is correct
9 Correct 11 ms 5764 KB Output is correct
10 Correct 10 ms 5588 KB Output is correct
11 Correct 11 ms 5716 KB Output is correct
12 Correct 9 ms 5844 KB Output is correct
13 Correct 11 ms 5760 KB Output is correct
14 Correct 11 ms 5684 KB Output is correct
15 Correct 11 ms 5628 KB Output is correct
16 Correct 8 ms 5588 KB Output is correct
17 Correct 8 ms 5688 KB Output is correct
18 Correct 5 ms 5428 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 31356 KB Output is correct
2 Correct 558 ms 31260 KB Output is correct
3 Correct 582 ms 31100 KB Output is correct
4 Correct 417 ms 30520 KB Output is correct
5 Correct 451 ms 33604 KB Output is correct
6 Correct 267 ms 32708 KB Output is correct
7 Correct 607 ms 33172 KB Output is correct
8 Correct 550 ms 31236 KB Output is correct
9 Correct 572 ms 33000 KB Output is correct
10 Correct 301 ms 24456 KB Output is correct
11 Correct 296 ms 30420 KB Output is correct
12 Correct 92 ms 20352 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 31356 KB Output is correct
2 Correct 558 ms 31260 KB Output is correct
3 Correct 582 ms 31100 KB Output is correct
4 Correct 417 ms 30520 KB Output is correct
5 Correct 451 ms 33604 KB Output is correct
6 Correct 267 ms 32708 KB Output is correct
7 Correct 607 ms 33172 KB Output is correct
8 Correct 550 ms 31236 KB Output is correct
9 Correct 572 ms 33000 KB Output is correct
10 Correct 301 ms 24456 KB Output is correct
11 Correct 296 ms 30420 KB Output is correct
12 Correct 92 ms 20352 KB Output is correct
13 Correct 597 ms 31768 KB Output is correct
14 Correct 586 ms 31820 KB Output is correct
15 Correct 572 ms 31368 KB Output is correct
16 Correct 418 ms 31032 KB Output is correct
17 Correct 507 ms 33720 KB Output is correct
18 Correct 254 ms 31680 KB Output is correct
19 Correct 600 ms 31892 KB Output is correct
20 Correct 605 ms 31820 KB Output is correct
21 Correct 590 ms 32240 KB Output is correct
22 Correct 285 ms 24544 KB Output is correct
23 Correct 293 ms 30372 KB Output is correct
24 Correct 100 ms 20460 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5036 KB Output is correct
4 Correct 2 ms 5032 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 12 ms 5716 KB Output is correct
8 Correct 11 ms 5756 KB Output is correct
9 Correct 11 ms 5764 KB Output is correct
10 Correct 10 ms 5588 KB Output is correct
11 Correct 11 ms 5716 KB Output is correct
12 Correct 9 ms 5844 KB Output is correct
13 Correct 11 ms 5760 KB Output is correct
14 Correct 11 ms 5684 KB Output is correct
15 Correct 11 ms 5628 KB Output is correct
16 Correct 8 ms 5588 KB Output is correct
17 Correct 8 ms 5688 KB Output is correct
18 Correct 5 ms 5428 KB Output is correct
19 Correct 562 ms 31356 KB Output is correct
20 Correct 558 ms 31260 KB Output is correct
21 Correct 582 ms 31100 KB Output is correct
22 Correct 417 ms 30520 KB Output is correct
23 Correct 451 ms 33604 KB Output is correct
24 Correct 267 ms 32708 KB Output is correct
25 Correct 607 ms 33172 KB Output is correct
26 Correct 550 ms 31236 KB Output is correct
27 Correct 572 ms 33000 KB Output is correct
28 Correct 301 ms 24456 KB Output is correct
29 Correct 296 ms 30420 KB Output is correct
30 Correct 92 ms 20352 KB Output is correct
31 Correct 597 ms 31768 KB Output is correct
32 Correct 586 ms 31820 KB Output is correct
33 Correct 572 ms 31368 KB Output is correct
34 Correct 418 ms 31032 KB Output is correct
35 Correct 507 ms 33720 KB Output is correct
36 Correct 254 ms 31680 KB Output is correct
37 Correct 600 ms 31892 KB Output is correct
38 Correct 605 ms 31820 KB Output is correct
39 Correct 590 ms 32240 KB Output is correct
40 Correct 285 ms 24544 KB Output is correct
41 Correct 293 ms 30372 KB Output is correct
42 Correct 100 ms 20460 KB Output is correct
43 Correct 651 ms 33400 KB Output is correct
44 Correct 613 ms 33756 KB Output is correct
45 Correct 624 ms 33668 KB Output is correct
46 Correct 444 ms 31948 KB Output is correct
47 Correct 484 ms 33996 KB Output is correct
48 Correct 283 ms 32572 KB Output is correct
49 Correct 661 ms 35728 KB Output is correct
50 Correct 598 ms 33572 KB Output is correct
51 Correct 644 ms 35656 KB Output is correct
52 Correct 312 ms 26144 KB Output is correct
53 Correct 302 ms 30968 KB Output is correct