QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#746072#8247. ICPC Team GenerationrahulmnavneethAC ✓0ms3844kbC++174.2kb2024-11-14 13:15:392024-11-14 13:15:39

Judging History

你现在查看的是最新测评结果

  • [2024-11-14 13:15:39]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3844kb
  • [2024-11-14 13:15:39]
  • 提交

answer

/*
        File: icpc-mock-141124-M-e_main.cpp
        Date and Time Created: 2024-11-14 10:40:12
        Author: Rahul M. Navneeth
*/

/* ----------------- HEADER FILES ----------------- */

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* ----------------- NAMESPACE ----------------- */

using namespace std;
using namespace chrono;
using namespace __gnu_pbds;

/* ----------------- TEMPLATES ------------------ */

/* clang-format off */

// MACROS
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define io freopen("./input.txt", "r", stdin); freopen("./output.txt", "w", stdout); freopen("./output.txt", "w", stderr);

// TYPEDEF
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; // POLICY BASED DS

// SHORTCUTS
#define ar array
#define pb push_back
#define pob pop_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second
#define UNIQUE_SORT(v) sort(all(v)); v.erase(unique(all(v)), v.end())

// FUNCTIONS
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void swap(int &x, int &y) { int temp = x; x = y; y = temp; }
ll combination(ll n, ll r, ll m, ll *fact, ll *ifact) { ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m; }
bool revsort(ll a, ll b) {return a > b;}
ll phin(ll n) {ll number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} //O(sqrt(N))
ll getRandomNumber(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);} 
vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll modpow(ll a, ll b, ll MOD) { ll res = 1; while(b > 0) { if(b & 1) { res = (res * a) % MOD; } b = b >> 1; a = (a*a) % MOD; } return res; }
void extendgcd(ll a, ll b, ll *v) { if (b == 0) { v[0] = 1; v[1] = 0; v[2] = a; return; }
extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return; } // PASS AN ARRY OF SIZE1 3
ll mminv(ll a, ll b) { ll arr[3]; extendgcd(a, b, arr); return arr[0]; } // FOR NON PRIME B
ll mminvprime(ll a, ll b) { return modpow(a, b - 2, b); }
ll mod_add(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a + b) % m) + m) % m; }
ll mod_mul(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a * b) % m) + m) % m; }
ll mod_sub(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a - b) % m) + m) % m; }
ll mod_div(ll a, ll b, ll m) { a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m; } // ONLY FOR PRIME M
void precision(int a) { cout << setprecision(a) << fixed; }

// CONSTANTS
const float PI = 3.141592653589793238462;
const int MOD = 1e9 + 7;
const int mxn = 1e7;
const int LOG = 30;

/* --------------------- CODE BEGINS ---------------------- */

void solve() {
	ll N; cin >> N;
	ar<ll, 2> a[N+1]; for(ll i = 1 ; i <= N ; i++) cin >> a[i][0] >> a[i][1];
	ll dp[N+1]; memset(dp, 0, sizeof dp);
	for(ll i = 3 ; i <= N; i++) {
		if(a[i][0] <= i-2 && a[i-2][1] >= i) {
			dp[i] = max(dp[i-1], dp[i-3]+1);
			continue;
		}
		dp[i] = dp[i-1];
	}
	cout << dp[N] << "\n";
    return;
}

/*---------------------- MAIN DRIVER ------------------------*/

// MAIN
int32_t main() {
  fast_io
  #ifndef ONLINE_JUDGE
    io;
  #endif
  high_resolution_clock::time_point start, end;
  #ifndef ONLINE_JUDGE
    start = chrono::high_resolution_clock::now();
  #endif
  int t = 1;
  int i = 1;
  // cin >> t;
  while (i <= t) {
  	#ifndef ONLINE_JUDGE
		cout << "TESTCASE #" << i << "\n";
	#endif
	i++;
    solve();
  }
  #ifndef ONLINE_JUDGE
    end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(end - start);
    cout << "-------------\nRUNTIME: " << duration.count() << " ms\n";
  #endif
  return 0;
}

/* clang-format on */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3844kb

input:

6
1 2
1 2
2 5
2 6
2 6
5 6

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

3
1 1
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

50
1 2
1 3
2 4
3 5
4 6
5 7
6 8
7 9
8 10
9 11
10 12
11 13
12 14
13 15
14 16
15 17
16 18
17 19
18 20
19 21
20 22
21 23
22 24
23 25
24 26
25 27
26 28
27 29
28 30
29 31
30 32
31 33
32 34
33 35
34 36
35 37
36 38
37 39
38 40
39 41
40 42
41 43
42 44
43 45
44 46
45 47
46 48
47 49
48 50
49 50

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50
1 50

output:

16

result:

ok single line: '16'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

50
1 11
2 11
3 12
3 14
3 15
3 16
7 17
7 17
7 18
8 19
11 21
11 22
11 22
14 23
15 25
16 25
17 25
18 27
18 27
20 29
21 30
22 30
22 33
23 34
24 34
24 34
25 37
28 37
29 38
29 38
31 41
32 41
33 43
33 43
35 44
35 46
36 47
37 47
38 48
39 49
39 50
41 50
42 50
44 50
45 50
45 50
45 50
47 50
48 50
48 50

output:

7

result:

ok single line: '7'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

50
1 8
2 12
2 13
3 14
3 14
5 16
5 16
6 18
9 18
9 20
9 20
12 21
12 21
12 21
14 24
16 24
17 26
17 26
18 27
20 29
20 30
22 30
22 32
24 32
25 35
25 36
25 36
25 36
26 37
30 38
31 41
32 41
33 41
34 43
35 43
35 44
35 44
37 48
37 49
40 50
41 50
41 50
41 50
42 50
44 50
45 50
47 50
47 50
47 50
49 50

output:

8

result:

ok single line: '8'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

50
1 7
1 12
3 12
4 14
4 14
4 14
6 14
6 14
8 14
10 18
11 19
12 22
12 22
14 22
14 25
14 26
14 26
16 26
17 29
18 30
18 31
18 32
22 32
23 34
23 35
25 35
26 35
26 37
26 37
30 40
31 40
32 41
33 42
33 44
33 45
33 46
33 47
34 47
39 48
39 50
39 50
39 50
41 50
42 50
45 50
45 50
45 50
45 50
45 50
48 50

output:

12

result:

ok single line: '12'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

50
1 2
2 6
2 7
4 8
5 12
5 15
6 16
8 16
8 19
8 20
8 20
8 21
13 22
13 24
13 25
13 25
16 25
16 25
16 29
20 29
21 30
22 31
22 33
23 33
24 33
25 33
27 33
27 37
28 38
28 39
30 41
32 42
32 42
34 42
34 42
36 45
37 45
37 47
37 47
40 49
40 50
40 50
43 50
43 50
43 50
46 50
46 50
48 50
49 50
50 50

output:

7

result:

ok single line: '7'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

50
1 8
1 11
2 13
4 13
5 13
6 15
7 15
8 16
8 17
10 19
10 21
11 22
11 22
11 22
12 25
12 25
16 26
17 28
19 28
20 29
20 30
20 31
23 31
23 31
24 33
25 35
26 37
27 38
28 38
30 40
31 40
31 42
31 43
32 44
32 45
34 45
35 45
35 47
38 49
38 50
38 50
42 50
43 50
44 50
44 50
46 50
47 50
47 50
49 50
50 50

output:

6

result:

ok single line: '6'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

50
1 6
1 7
1 8
2 8
2 10
3 10
3 12
6 13
9 13
10 14
11 16
12 16
12 17
12 19
12 19
14 19
16 19
16 20
18 24
19 25
20 25
22 25
23 26
23 29
23 29
23 29
26 29
26 33
29 33
30 33
31 36
31 36
32 37
32 37
35 38
35 41
35 41
36 41
37 43
38 45
38 45
42 47
42 48
44 49
45 49
45 50
45 50
47 50
47 50
49 50

output:

10

result:

ok single line: '10'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

50
1 1
2 2
2 5
2 8
3 10
6 10
7 10
8 12
9 12
10 14
10 15
11 16
11 17
14 18
15 18
15 20
15 22
16 22
17 24
20 24
21 25
22 25
23 26
24 28
24 28
25 30
27 30
27 33
29 34
30 35
31 36
32 36
32 36
34 39
35 39
36 40
37 42
38 42
38 43
38 43
38 44
38 46
41 48
41 49
41 49
44 49
47 50
47 50
48 50
50 50

output:

6

result:

ok single line: '6'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

50
1 1
1 4
1 7
4 8
5 8
5 10
6 12
6 12
6 12
6 12
6 16
11 17
13 18
13 19
15 19
16 21
17 22
17 22
17 22
17 23
17 23
21 24
23 25
24 26
24 29
24 30
24 30
25 33
25 33
28 33
29 34
29 34
29 34
29 36
32 39
32 40
33 40
33 40
38 44
39 45
39 46
39 47
42 48
43 48
45 48
46 48
46 49
46 49
46 49
50 50

output:

9

result:

ok single line: '9'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

50
1 1
1 2
3 3
4 7
5 7
5 7
7 8
8 12
9 14
9 15
9 15
9 15
12 17
13 17
15 17
15 21
17 22
17 23
17 23
19 25
19 25
21 25
22 28
24 29
24 30
24 31
27 32
27 32
29 33
29 34
29 36
30 37
32 37
32 39
34 40
36 41
36 41
36 42
36 44
38 45
39 46
40 47
40 48
42 49
43 50
43 50
47 50
47 50
47 50
50 50

output:

9

result:

ok single line: '9'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

50
1 3
2 7
3 8
4 9
4 10
5 11
7 11
8 11
9 11
10 11
10 11
11 16
12 16
14 17
14 17
15 20
16 20
17 20
18 23
18 24
20 24
22 24
22 27
23 29
24 30
26 31
27 31
28 33
29 34
30 35
30 36
30 36
32 37
33 39
34 40
36 41
37 41
37 42
39 43
40 44
40 45
42 46
43 46
44 49
44 50
44 50
45 50
48 50
49 50
50 50

output:

3

result:

ok single line: '3'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

25
1 6
1 6
2 7
2 9
5 10
5 11
5 12
5 13
7 14
7 14
7 15
11 15
13 16
13 19
15 19
16 20
16 21
17 23
18 24
20 25
21 25
21 25
23 25
23 25
24 25

output:

3

result:

ok single line: '3'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

42
1 1
2 3
2 5
4 5
4 6
4 8
5 9
8 11
9 12
10 14
10 15
10 17
12 18
12 19
14 20
15 21
15 21
18 23
19 24
19 24
20 26
22 27
23 28
24 29
24 29
26 29
26 31
28 32
28 33
29 34
31 34
31 34
32 38
34 38
35 38
36 41
37 41
38 42
38 42
39 42
39 42
42 42

output:

3

result:

ok single line: '3'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

29
1 4
1 5
1 6
3 7
4 10
4 10
6 11
8 11
9 13
10 14
11 15
12 15
12 15
14 19
14 19
16 19
17 21
17 21
17 24
18 24
20 26
21 26
21 28
23 28
25 29
26 29
27 29
27 29
27 29

output:

5

result:

ok single line: '5'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

41
1 1
1 2
1 5
4 6
4 9
5 10
5 11
7 11
9 12
10 13
10 15
10 17
12 18
14 19
14 19
16 19
16 21
18 22
19 24
20 25
21 26
21 27
22 28
23 29
23 30
24 31
25 31
26 31
27 32
27 34
29 36
32 37
33 38
34 38
34 39
35 39
36 41
38 41
39 41
40 41
41 41

output:

5

result:

ok single line: '5'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

44
1 1
2 5
2 6
4 8
4 10
5 11
6 12
6 13
8 13
8 14
8 14
11 15
13 17
14 18
14 19
15 19
17 21
17 22
17 24
18 24
19 25
19 26
19 26
23 26
23 27
24 30
24 31
25 32
29 34
29 35
29 35
31 37
33 38
33 39
34 39
35 41
36 42
38 43
39 43
39 43
41 44
41 44
43 44
43 44

output:

7

result:

ok single line: '7'