Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
int L, v, l, r;
cin >> L >> v >> l >> r;
cout << L / v - r / v + (l - 1) / v << endl;
}
return 0;
}
Tutorial
Tutorial is loading...
Solution 1
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, r;
cin >> n >> r;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int ans = 0;
int last = -1;
while (last < n - 1) {
int pos = -1;
for (int i = n - 1; i > max(-1, last - r + 1); --i) {
if (a[i] == 1 && i - r <= last) {
pos = i;
break;
}
}
if (pos == -1) {
cout << -1 << "\n";
return 0;
}
++ans;
last = pos + r - 1;
}
cout << ans << "\n";
return 0;
}
Solution 2
#include <vector>
#include <iostream>
#define forn(i,n) for (int i=0; i<int(n); i++)
using namespace std;
const int N = 2e5;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, r; cin >> n >> r;
vector<int> a(n);
vector<int> cnt(n);
int ans = 0;
forn(i, n)
{
cin >> a[i];
if (a[i])ans++;
if (a[i])
for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
cnt[j]++;
}
forn(i, n)
if (!cnt[i])
{
cout << -1;
return 0;
}
forn(i, n)
{
bool fl = true;
if (a[i])
for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
if (cnt[j] == 1)
{
fl = false;
break;
}
if (fl && a[i])
{
ans--;
for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
cnt[j]--;
}
}
cout << ans;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int M = 200 * 1000 + 11;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
vector<int> pos(M);
int curl = 0;
int curr = 0;
for (int i = 0; i < q; ++i) {
string type;
int id;
cin >> type >> id;
if (i == 0) {
pos[id] = curl;
--curl;
++curr;
} else {
if (type == "L") {
pos[id] = curl;
--curl;
} else if (type == "R") {
pos[id] = curr;
++curr;
} else {
cout << min(abs(pos[id] - curl), abs(pos[id] - curr)) - 1 << "\n";
}
}
}
return 0;
}
Tutorial
Tutorial is loading...
Solution 1
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 10;
int ar[MAX];
int n, m, k;
int find(int pos){
int ans = n - pos + 1;
int used = 0;
while(used < m && pos <= n){
int t = k;
while(pos <= n && ar[pos] <= t){
t -= ar[pos++];
}
used++;
}
return pos == n + 1 ? ans : 0;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
cin >> ar[i];
}
int ans = 0;
int l = 1, r = n;
while(l <= r){
int x = (l + r) >> 1;
if(find(x)){
ans = max(ans, n - x + 1);
r = x - 1;
}else{
l = x + 1;
}
}
cout << ans << endl;
}
Solution 2
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
reverse(a.begin(), a.end());
int rem = 0;
for (int i = 0; i < n; ++i) {
if (rem - a[i] < 0) {
if (m == 0) {
cout << i << endl;
return 0;
} else {
--m;
rem = k - a[i];
}
} else {
rem -= a[i];
}
}
cout << n << endl;
return 0;
}
1066E - Binary Numbers AND Sum
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int a, int b) {
a += b;
if (a < 0) a += MOD;
if (a >= MOD) a -= MOD;
return a;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m;
cin >> n >> m;
string s, t;
cin >> s >> t;
int pw = 1;
int res = 0;
int ans = 0;
for (int i = 0; i < m; ++i) {
if (i < n && s[n - i - 1] == '1') {
res = add(res, pw);
}
if (t[m - i - 1] == '1') {
ans = add(ans, res);
}
pw = add(pw, pw);
}
cout << ans << endl;
return 0;
}
1066F - Yet another 2D Walking
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const long long INF64 = 1e18;
long long dist(pair<int, int> a, pair<int, int> b) {
return abs(a.first - b.first) + abs(a.second - b.second);
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
map<int, vector<pair<int, int>>> pts;
cin >> n;
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
pts[max(x, y)].push_back(make_pair(x, y));
}
pts[0].push_back(make_pair(0, 0));
for (auto &it : pts) {
sort(it.second.begin(), it.second.end(), [&](pair<int, int> a, pair<int, int> &b) {
if (a.first == b.first)
return a.second > b.second;
return a.first < b.first;
});
}
vector<vector<long long>> dp(int(pts.size()) + 1, vector<long long>(2, INF64));
dp[0][0] = dp[0][1] = 0;
int lvl = 0;
int prv = 0;
for (auto &it : pts) {
++lvl;
pair<int, int> curl = it.second[0];
pair<int, int> curr = it.second.back();
pair<int, int> prvl = pts[prv][0];
pair<int, int> prvr = pts[prv].back();
dp[lvl][0] = min(dp[lvl][0], dp[lvl - 1][0] + dist(prvl, curr) + dist(curl, curr));
dp[lvl][0] = min(dp[lvl][0], dp[lvl - 1][1] + dist(prvr, curr) + dist(curl, curr));
dp[lvl][1] = min(dp[lvl][1], dp[lvl - 1][0] + dist(prvl, curl) + dist(curl, curr));
dp[lvl][1] = min(dp[lvl][1], dp[lvl - 1][1] + dist(prvr, curl) + dist(curl, curr));
prv = it.first;
}
cout << min(dp[lvl][0], dp[lvl][1]) << endl;
return 0;
}