Tutorial
Tutorial is loading...
Solution (BledDest)
q = int(input())
for i in range(q):
l, r, d = map(int, input().split())
if(d < l or d > r):
print(d)
else:
print((r // d) * d + d)
Tutorial
Tutorial is loading...
Solution (Vovuh)
#include <bits/stdc++.h>
using namespace std;
void rem(string &s, const string &c) {
auto pos = s.find(c);
if (pos == string::npos) {
cout << -1 << endl;
exit(0);
}
s.erase(0, pos + 1);
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
string s;
cin >> s;
rem(s, "[");
rem(s, ":");
reverse(s.begin(), s.end());
rem(s, "]");
rem(s, ":");
cout << count(s.begin(), s.end(), '|') + 4 << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> pt;
int n;
vector< pair<pt, int> > segs;
inline bool read() {
if(!(cin >> n))
return false;
segs.resize(n);
for(int i = 0; i < n; i++) {
cin >> segs[i].x.x >> segs[i].x.y;
segs[i].y = i;
}
return true;
}
bool cmp(const pair<pt, int> &a, const pair<pt, int> &b) {
if(a.x.y != b.x.y)
return a.x.y < b.x.y;
if(a.x.x != b.x.x)
return a.x.x < b.x.x;
return a.y < b.y;
}
inline void solve() {
sort(segs.begin(), segs.end(), cmp);
int mn = segs[n - 1].x.x;
for(int i = n - 2; i >= 0; i--) {
if(segs[i].x.y < mn) {
vector<int> ts(n, 2);
for(int id = 0; id <= i; id++)
ts[segs[id].y] = 1;
for(int t : ts)
cout << t << ' ';
cout << '\n';
return;
}
mn = min(mn, segs[i].x.x);
}
cout << -1 << '\n';
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int tc;
cin >> tc;
while(tc--) {
assert(read());
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (PikMike)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
return out << "(" << a.x << ", " << a.y << ")";
}
template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
out << "[";
forn(i, sz(v)) {
if(i) out << ", ";
out << v[i];
}
return out << "]";
}
mt19937 rnd(time(NULL));
const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = INF + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);
const int N = 200 * 1000 + 13;
int n;
int a[N];
vector<int> g[N];
bool read () {
if (scanf("%d", &n) != 1)
return false;
forn(i, n)
g[i].clear();
forn(i, n)
scanf("%d", &a[i]);
forn(i, n - 1){
int x, y;
scanf("%d%d", &x, &y);
--x, --y;
g[x].pb(y);
g[y].pb(x);
}
return true;
}
vector<pt> dp[N];
int ans;
void calc(int v, int p = -1){
vector<pt> chd;
for (auto u : g[v]) if (u != p){
calc(u, v);
for (auto it : dp[u])
chd.pb(it);
}
sort(all(chd));
forn(i, sz(chd)){
int j = i - 1;
int mx1 = 0, mx2 = 0;
while (j + 1 < sz(chd) && chd[j + 1].x == chd[i].x){
++j;
if (chd[j].y >= mx1)
mx2 = mx1, mx1 = chd[j].y;
else if (chd[j].y > mx2)
mx2 = chd[j].y;
}
if (a[v] % chd[i].x == 0){
ans = max(ans, mx1 + mx2 + 1);
dp[v].pb(mp(chd[i].x, mx1 + 1));
while (a[v] % chd[i].x == 0)
a[v] /= chd[i].x;
}
else{
ans = max(ans, mx1);
}
i = j;
}
for (int i = 2; i * i <= a[v]; ++i) if (a[v] % i == 0){
dp[v].pb(mp(i, 1));
ans = max(ans, 1);
while (a[v] % i == 0)
a[v] /= i;
}
if (a[v] > 1){
dp[v].pb(mp(a[v], 1));
ans = max(ans, 1);
}
}
void solve() {
forn(i, N) dp[i].clear();
ans = 0;
calc(0);
printf("%d\n", ans);
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int tt = clock();
#endif
cerr.precision(15);
cout.precision(15);
cerr << fixed;
cout << fixed;
#ifdef _DEBUG
while(read()) {
#else
if (read()){
#endif
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
}
Tutorial
Tutorial is loading...
Solution (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int n;
scanf("%d", &n);
int mxa = 0, mxb = 0;
static char buf[5];
forn(i, n){
int x, y;
scanf("%s%d%d", buf, &x, &y);
if (x < y)
swap(x, y);
if (buf[0] == '+'){
mxa = max(mxa, x);
mxb = max(mxb, y);
}
else{
puts(mxa <= x && mxb <= y ? "YES" : "NO");
}
}
}
Tutorial
Tutorial is loading...
Solution 1 (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define mp make_pair
#define pb push_back
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int INF = int(1e9);
const int N = 411;
int n, m;
int a[N];
vector< pair<pt, pt> > qs;
inline bool read() {
if(!(cin >> n >> m))
return false;
fore(i, 0, n)
cin >> a[i];
qs.resize(m);
fore(i, 0, m) {
cin >> qs[i].x.x >> qs[i].x.y >> qs[i].y.x >> qs[i].y.y;
qs[i].x.x--; qs[i].x.y--;
}
return true;
}
vector<int> ids[N];
int d[N][N];
inline void solve() {
fore(i, 0, m)
ids[qs[i].x.x].push_back(i);
li ans = -1;
fore(l, 0, n) {
fore(r, l, n)
d[0][r] = a[r] - a[l];
fore(k, 1, n + 1) {
int opt = l;
fore(r, l, n) {
while(opt < r && max(d[k - 1][opt], a[r] - a[opt]) >= max(d[k - 1][opt + 1], a[r] - a[opt + 1]))
opt++;
d[k][r] = max(d[k - 1][opt], a[r] - a[opt]);
}
}
for(int id : ids[l])
ans = max(ans, d[qs[id].y.y][qs[id].x.y] * 1ll * qs[id].y.x);
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Solution 2 (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define mp make_pair
#define pb push_back
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
const int N = 411;
int n, m;
int a[N];
vector< pair<pt, pt> > qs;
inline bool read() {
if(!(cin >> n >> m))
return false;
fore(i, 0, n)
cin >> a[i];
qs.resize(m);
fore(i, 0, m) {
cin >> qs[i].x.x >> qs[i].x.y >> qs[i].y.x >> qs[i].y.y;
qs[i].x.x--; qs[i].x.y--;
}
return true;
}
int getCnt(const pair<pt, pt> &q, li mx) {
li dist = mx / q.y.x;
int s = q.x.x, f = q.x.y;
int u = s, cnt = 0;
while(u < f) {
int v = u;
while(v < f && a[v + 1] - a[u] <= dist)
v++;
if(v == u)
return INF;
cnt++;
u = v;
}
return cnt - 1;
}
li upd(const pair<pt, pt> &q, li lf, li rg) {
if(getCnt(q, lf) <= q.y.y)
return lf;
while(rg - lf > 1) {
li mid = (lf + rg) >> 1;
(getCnt(q, mid) <= q.y.y ? rg : lf) = mid;
}
return rg;
}
inline unsigned int getHash(const vector<int> &vals) {
unsigned int hash = 0;
for(int v : vals)
hash = hash * 3 + v;
return hash;
}
inline void solve() {
auto seed = getHash(vector<int>(a, a + n));
fore(i, 0, m)
seed = seed * 3 + getHash({qs[i].x.x, qs[i].x.y, qs[i].y.x, qs[i].y.y});
mt19937 rnd(seed);
vector<int> ids(m, 0);
iota(all(ids), 0);
shuffle(all(ids), rnd);
li curv = 0;
for(int id : ids)
curv = upd(qs[id], curv, 2 * INF64);
cout << curv << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
1101G - (Zero XOR Subset)-less
Tutorial
Tutorial is loading...
Solution (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 200 * 1000 + 13;
const int LOGN = 30;
int n;
int a[N], pr[N];
int base[LOGN];
void try_gauss(int v){
for(int i = LOGN - 1; i >= 0; i--)
if (base[i] != -1 && (v & (1 << i)))
v ^= base[i];
if (v == 0)
return;
for(int i = LOGN - 1; i >= 0; i--) if (v & (1 << i)){
base[i] = v;
return;
}
}
int main() {
scanf("%d", &n);
forn(i, n)
scanf("%d", &a[i]);
memset(base, -1, sizeof(base));
forn(i, n){
pr[i + 1] = pr[i] ^ a[i];
try_gauss(pr[i + 1]);
}
if (pr[n] == 0){
puts("-1");
return 0;
}
int siz = 0;
forn(i, LOGN)
siz += (base[i] != -1);
printf("%d\n", siz);
}