Idea: senjougaharin
Tutorial
Tutorial is loading...
Solution
for _ in range(int(input())):
a = int(input())
if 102 <= a <= 109 or 1010 <= a <= 1099:
print("YES")
else:
print("NO")
Idea: myav
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
vector<int>a(n);
for(auto &i : a) cin >> i;
int left = a[0], right = a[0];
for(int i = 1; i < n; i++){
if(a[i] + 1 == left) left = a[i];
else if(a[i] - 1 == right) right = a[i];
else {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
int main(){
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
2000C - Numeric String Template
Idea: myav
Tutorial
Tutorial is loading...
Solution
def solve():
n = int(input())
a = list(map(int, input().split()))
m = int(input())
for _ in range(m):
m_1 = {}
m_2 = {}
s = input().strip()
if len(s) != n:
print("NO")
continue
ok = True
for j in range(n):
if s[j] not in m_1 and a[j] not in m_2:
m_1[s[j]] = a[j]
m_2[a[j]] = s[j]
elif (s[j] in m_1 and m_1[s[j]] != a[j]) or (a[j] in m_2 and m_2[a[j]] != s[j]):
ok = False
break
print("YES" if ok else "NO")
t = int(input())
for _ in range(t):
solve()
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
def solve():
n = int(input())
a = [0]
for x in input().split():
x = int(x)
a.append(a[-1] + x)
s = input()
ans = 0
l = 0
r = n - 1
while r > l:
while l < n and s[l] == 'R':
l += 1
while r >= 0 and s[r] == 'L':
r -= 1
if l < r:
ans += a[r + 1] - a[l]
l += 1
r -= 1
print(ans)
t = int(input())
for _ in range(t):
solve()
2000E - Photoshoot for Gorillas
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define MAXW 200200
#define MAXNM 200200
int n, m, k, w, p;
int arr[MAXW], prr[MAXNM];
static inline int calcc(int i, int j) {
int upr = min(i, n - k);
int leftr = min(j, m - k);
int upl = max(-1LL, i - k);
int leftl = max(-1LL, j - k);
return (upr - upl) * (leftr - leftl);
}
void build() {
sort(arr, arr + w);
reverse(arr, arr + w);
p = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
prr[p++] = calcc(i, j);
sort(prr, prr + p);
reverse(prr, prr + p);
}
int solve() {
int sum = 0;
for (int i = 0; i < w; ++i)
sum += prr[i] * arr[i];
return sum;
}
signed main() {
int t; cin >> t;
while (t--) {
cin >> n >> m >> k >> w;
for (int i = 0; i < w; ++i)
cin >> arr[i];
build();
cout << solve() << endl;
}
}
2000F - Color Rows and Columns
Idea: senjougaharin
Tutorial
Tutorial is loading...
Solution
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
}
vector<vector<int>> dp(n + 1, vector<int>(k + 1, 1e9));
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
int x = a[i], y = b[i];
int xy = x + y;
int cost = 0;
for (int j = 0; j <= xy; ++j) {
for (int j1 = 0; j1 + j <= k; ++j1) {
dp[i + 1][j1 + j] = min(dp[i + 1][j1 + j], dp[i][j1] + cost);
}
if (j < xy) {
if (x >= y) {
x--, cost += y;
} else {
y--, cost += x;
}
}
}
}
cout << (dp[n][k] == 1e9 ? -1 : dp[n][k]) << '\n';
}
int main() {
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}
2000G - Call During the Journey
Idea: senjougaharin
Tutorial
Tutorial is loading...
Solution
#include <iostream>
#include <vector>
#include <set>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
int t0, t1, t2;
cin >> t0 >> t1 >> t2;
vector<vector<vector<int>>> g(n);
for (int i = 0; i < m; ++i) {
int u, v, l1, l2;
cin >> u >> v >> l1 >> l2;
u--, v--;
g[u].push_back({v, l1, l2});
g[v].push_back({u, l1, l2});
}
set<pair<int, int>> prq;
prq.insert({t0, n - 1});
for (int i = 0; i + 1 < n; ++i) {
prq.insert({-1e9, i});
}
vector<int> dist(n, -1e9);
dist[n - 1] = t0;
while (!prq.empty()) {
auto p = *prq.rbegin();
prq.erase(p);
int d = p.first, u = p.second;
for (auto e: g[u]) {
int v = e[0], l1 = e[1], l2 = e[2];
int d1 = (d - l1 >= t2 || d <= t1) ? d - l1 : d - l2;
if(d1 == d - l2) d1 = max(d1, t1 - l1);
if (dist[v] < d1) {
prq.erase({dist[v], v});
dist[v] = d1;
prq.insert({d1, v});
}
}
}
cout << (dist[0] >= 0 ? dist[0] : -1) << '\n';
}
int main() {
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}
2000H - Ksyusha and the Loaded Set
Idea: senjougaharin
Tutorial
Tutorial is loading...
Solution
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef pair<int, int> ipair;
#define INF 1'000'000'009
#define MAXN 200200
#define MAXMEM 5'000'000
#define MAXLEN 2'000'100
#define X first
#define Y second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node {
node *lv = nullptr, *rv = nullptr;
ipair key;
int prior;
int minl = INF;
node(const ipair& key) : key(key), prior(rng()), minl(key.Y) {}
};
static inline int minl(node *v) {
return (v == nullptr ? INF : v->minl);
}
static inline void upd(node *v) {
v->minl = min(v->key.Y, min(minl(v->lv), minl(v->rv)));
}
node *merge(node *s1, node *s2) {
if (s1 == nullptr) return s2;
if (s2 == nullptr) return s1;
if (s1->prior > s2->prior) {
s1->rv = merge(s1->rv, s2);
upd(s1);
return s1;
} else {
s2->lv = merge(s1, s2->lv);
upd(s2);
return s2;
}
}
pair<node*, node*> split(node* &v, ipair x) {
if (v == nullptr) {
return {nullptr, nullptr};
}
if (v->key < x) {
auto [s1, s2] = split(v->rv, x);
v->rv = s1;
upd(v);
return {v, s2};
} else {
auto [s1, s2] = split(v->lv, x);
v->lv = s2;
upd(v);
return {s1, v};
}
}
int n, m;
int arr[MAXN];
node *mem = (node*)calloc(MAXMEM, sizeof(*mem));
node *mpos = mem;
node *root;
set<int> M;
// [l..r)
void add_seg(int l, int r) {
if (l >= r) return;
ipair p {r - l, l};
auto [s1, s2] = split(root, p);
node *v = mpos++;
*v = node(p);
root = merge(merge(s1, v), s2);
}
void rem_dek(node* &v, const ipair& x) {
if (v == nullptr) return;
if (v->key == x) {
v = merge(v->lv, v->rv);
if (v) upd(v);
return;
}
if (v->key < x) rem_dek(v->rv, x);
else rem_dek(v->lv, x);
upd(v);
}
// [l..r)
void rem_seg(int l, int r) {
if (l >= r) return;
ipair p {r - l, l};
rem_dek(root, p);
}
void add_val(int x) {
auto it = M.lower_bound(x);
int clsl = (it == M.begin() ? 0 : *prev(it));
int clsr = (it == M.end() ? INF : *it);
rem_seg(clsl + 1, clsr);
add_seg(clsl + 1, x);
if (clsr != INF) add_seg(x + 1, clsr);
M.insert(x);
}
void rem_val(int x) {
auto it = M.lower_bound(x);
int clsl = (it == M.begin() ? 0 : *prev(it));
int clsr = (next(it) == M.end() ? INF : *next(it));
rem_seg(clsl + 1, x);
rem_seg(x + 1, clsr);
if (clsr != INF) add_seg(clsl + 1, clsr);
M.erase(x);
}
int query(int k) {
if (M.empty()) return 1;
auto [s1, s2] = split(root, make_pair(k, -1));
fprintf(stderr, "AMOGUS: %p, %p\n", s1, s2);
int ans = min(*M.rbegin() + 1, minl(s2));
root = merge(s1, s2);
return ans;
}
void init() {
root = nullptr;
mpos = mem;
M = {arr, arr + n};
add_seg(1, *M.begin());
for (auto it = M.begin(); next(it) != M.end(); ++it)
add_seg(*it + 1, *next(it));
}
signed main() {
int t; cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> arr[i];
init();
cin >> m;
for (int j = 0; j < m; ++j) {
char tp; cin >> tp;
int x, k;
switch (tp) {
case '+':
cin >> x;
add_val(x);
break;
case '-':
cin >> x;
rem_val(x);
break;
case '?':
cin >> k;
cout << query(k) << " ";
break;
}
}
cout << endl;
}
}
can anyone pls tell why this code is getting a runtime error. for Problem D
And also the issue with the algo pls.
consider the case where there are no 'R' in the string. in this scenario, your 'right' variable would be initialized with the value -1
edit : avoid using C++17 (GCC 7-32) and use C++20 (GCC 13-64) instead
you mean something like this -> n = 6, a(n) = 1 1 1 1 1 1 s = LLLLLL -> and the output should be 0 right. actually I checked this one already and it gives me 0 perfectly fine. Cause I'm checking the out of bound condition before using those
I admit I do not know much about C++17 (32-bit), but if I had to guess, this particular error might be occurring because your while loop condition:
while(left < leftsig.size() && right >= 0 && leftsig[left] < rightsig[right]) {
is not stopping after
right >= 0
evaluates tofalse
. Instead, it continues evaluatingleftsig[left] < rightsig[right]
, which could cause an access violation if right is-1
and thus result in the erroryou can fix it by choosing C++20 (GCC 13-64) as your compiler when you submit the code
https://mirror.codeforces.com/contest/2000/submission/276452095
yeah I guess C++17 doesn't stop when a condition is false in the loop conditions, untill it checks all the conditions
edit: I used the prefix sum to avoid tle and it went ohk
oh thanks for the help it went perfectly just by changing this. Wasn't expecting it to be this sort of issue, will use C++ 20 always :) .
This solution will give tle as you are calculating sum of subarray again and again. Instead use prefix sum to get the sum of the subarray.
I did that that in the updated code here ->
But this still gives me runtime error
I need help
Can anyone tell me why my solution in proplem E got TLE when i write it in java , but when i write the same code in c++ i got AC
java solution --> Your text to link here...
c++ solution --> Your text to link here...
someone explain how to intuit the way they count it in problem E please.
I am impressed by how treap is being casually used in a div3 contest editorial (problem H).
(Context: Of course I am well aware that this is not how most contestants solved, or are supposed to solve it, but rather make use of the (non-essential) constraints max <= 2e6. It is also clear that a fully online solution of this without the extra constraints will have to involve your favourite BBST. Though, I don't know how many people will get confused by the editorial. )
They took the effort to explain the std::set part but not the treap part :)
for E, I completely missed the
n*m<=2e5
bound and coded aO(nlogn + mlogm + wlog(n*m))
solution276188663
I also misread the n*m<=2e5 constraint, and I tried to code a bfs type solution starting from the center of the grid where we greedily visit cells in the graph that have the most subarrays containing them. I failed in the implementation, but is your solution idea similar?
yes, similar, that's pretty much what I did
I got scared when I didn't see the
n*m <= 2e5
condition and I immediately re-checked the problem statement :)🆗