QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#746072 | #8247. ICPC Team Generation | rahulmnavneeth | AC ✓ | 0ms | 3844kb | C++17 | 4.2kb | 2024-11-14 13:15:39 | 2024-11-14 13:15:39 |
Judging History
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'