Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> pos(n / 2);
for (int i = 0; i < n / 2; ++i)
cin >> pos[i];
sort(pos.begin(), pos.end());
int ans1 = 0, ans2 = 0;
for (int i = 0; i < n / 2; ++i) {
ans1 += abs(pos[i] - (i * 2 + 1));
ans2 += abs(pos[i] - (i * 2 + 2));
}
cout << min(ans1, ans2) << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<string> s(n);
vector<int> cnt(m);
for (int i = 0; i < n; ++i) {
cin >> s[i];
for (int j = 0; j < m; ++j)
if (s[i][j] == '1') ++cnt[j];
}
for (int i = 0; i < n; ++i) {
bool ok = true;
for (int j = 0; j < m; ++j) {
if (s[i][j] == '1' && cnt[j] == 1)
ok = false;
}
if (ok) {
puts("YES");
return 0;
}
}
puts("NO");
return 0;
}
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
typedef long long li;
int n, k, l, m;
vector<li> a;
inline bool read() {
if(!(cin >> n >> k >> l))
return false;
m = n * k;
a.assign(m, 0);
fore(i, 0, m)
assert(scanf("%lld", &a[i]) == 1);
return true;
}
inline void solve() {
sort(a.begin(), a.end());
int rg = int(upper_bound(a.begin(), a.end(), a[0] + l) - a.begin());
if(rg < n) {
puts("0");
return;
}
li ans = 0;
int u = 0;
fore(i, 0, n) {
ans += a[u++];
fore(j, 0, k - 1) {
if(rg - u > n - i - 1)
u++;
else
break;
}
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cerr << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Разбор
Tutorial is loading...
Решение (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
typedef long long li;
using namespace std;
const int INF = 2e9;
li n, h;
bool check(li maxh){
li k = min(h, maxh);
li cnt = maxh * maxh - k * (k - 1) / 2;
return (cnt <= n);
}
li get(li maxh){
li k = min(h, maxh);
li cnt = maxh * maxh - k * (k - 1) / 2;
li len = (2 * maxh - 1) - (k - 1);
n -= cnt;
return len + (n + maxh - 1) / maxh;
}
int main() {
scanf("%lld%lld", &n, &h);
li l = 1, r = INF;
while (l < r - 1){
li m = (l + r) / 2;
if (check(m))
l = m;
else
r = m;
}
printf("%lld\n", check(r) ? get(r) : get(l));
return 0;
}
Разбор
Tutorial is loading...
Решение (PikMike)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
const int N = 500 * 1000 + 13;
int f[N];
void upd(int x){
for (int i = x; i < N; i |= i + 1)
++f[i];
}
int sum(int x){
int res = 0;
for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
res += f[i];
return res;
}
int get(int l, int r){
if (l > r) return 0;
return sum(r) - sum(l - 1);
}
int main(){
int n, k, dif;
scanf("%d%d%d", &n, &k, &dif);
vector<int> a(n);
forn(i, n)
scanf("%d", &a[i]);
sort(a.begin(), a.end());
vector<int> dp(n + 1, 0);
dp[0] = 1;
upd(0);
int l = 0;
forn(i, n){
while (l < i && a[i] - a[l] > dif)
++l;
dp[i + 1] = (get(l, i - k + 1) >= 1);
if (dp[i + 1]) upd(i + 1);
}
puts(dp[n] ? "YES" : "NO");
}
Разбор
Tutorial is loading...
Решение (adedalic)
#include <bits/stdc++.h>
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int(a.size())
#define x first
#define y second
using namespace std;
const int B = 2;
typedef array<int, B> ht;
ht MOD, BASE;
inline int norm(int a, const int &MOD) {
while(a >= MOD)
a -= MOD;
while(a < 0)
a += MOD;
return a;
}
inline int mul(int a, int b, const int &MOD) {
return int(a * 1ll * b % MOD);
}
inline ht operator +(const ht &a, const ht &b) {
ht ans;
fore(i, 0, sz(ans))
ans[i] = norm(a[i] + b[i], MOD[i]);
return ans;
}
inline ht operator -(const ht &a, const ht &b) {
ht ans;
fore(i, 0, sz(ans))
ans[i] = norm(a[i] - b[i], MOD[i]);
return ans;
}
inline ht operator *(const ht &a, const ht &b) {
ht ans;
fore(i, 0, sz(ans))
ans[i] = mul(a[i], b[i], MOD[i]);
return ans;
}
int CMODS[] = {int(1e9) + 7, int(1e9) + 9, int(1e9) + 21, int(1e9) + 33, int(1e9) + 87, int(1e9) + 93, int(1e9) + 97, int(1e9) + 103};
int CBASE[] = {1009, 1013, 1019, 1021};
const int N = 200 * 1000 + 555;
int n, m;
char s[N];
int x[N], y[N], len[N];
inline bool read() {
if(!(cin >> n >> m))
return false;
assert(scanf("%s", s) == 1);
fore(i, 0, m) {
assert(scanf("%d%d%d", &x[i], &y[i], &len[i]) == 3);
x[i]--, y[i]--;
}
return true;
}
void setMods() {
mt19937 rnd;
unsigned int seed = n;
fore(i, 0, n)
seed = (seed * 3) + s[i];
fore(i, 0, m) {
seed = (seed * 3) + x[i];
seed = (seed * 3) + y[i];
seed = (seed * 3) + len[i];
}
rnd.seed(seed);
set<int> mids;
while(sz(mids) < sz(MOD))
mids.insert(rnd() % 8);
vector<int> vmids(mids.begin(), mids.end());
fore(i, 0, sz(MOD)) {
MOD[i] = CMODS[vmids[i]];
BASE[i] = CBASE[i];
}
}
ht pBase[N];
ht ph[27][N];
vector<int> ord[N];
ht getHash(int id, int l, int r) {
return ph[id][r] - ph[id][l] * pBase[r - l];
}
inline void solve() {
setMods();
pBase[0] = {1, 1};
fore(i, 1, N)
pBase[i] = pBase[i - 1] * BASE;
fore(c, 0, 26) {
ph[c][0] = {0, 0};
fore(i, 0, n) {
int val = (s[i] == c + 'a');
ph[c][i + 1] = ph[c][i] * BASE + ht{val, val};
}
}
vector<int> curOrd(26, 0);
iota(curOrd.begin(), curOrd.end(), 0);
for(int i = n - 1; i >= 0; i--) {
ord[i] = curOrd;
auto it = find(ord[i].begin(), ord[i].end(), int(s[i] - 'a'));
ord[i].erase(it);
ord[i].insert(ord[i].begin(), int(s[i] - 'a'));
curOrd = ord[i];
}
fore(q, 0, m) {
int s1 = x[q], s2 = y[q];
bool ok = true;
fore(i, 0, 26) {
if(getHash(ord[s1][i], s1, s1 + len[q]) !=
getHash(ord[s2][i], s2, s2 + len[q])) {
ok = false;
break;
}
}
puts(ok ? "YES" : "NO");
}
}
int main(){
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
if(read()) {
solve();
}
return 0;
}
Разбор
Tutorial is loading...
Решение (adedalic)
#include <bits/stdc++.h>
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int(a.size())
using namespace std;
typedef unsigned long long uli;
const int N = 200 * 1000 + 555;
int n, m;
uli a, b, c;
vector<int> g[N];
inline bool read() {
if(!(cin >> n >> m))
return false;
assert(cin >> a >> b >> c);
fore(i, 0, m) {
int u, v;
assert(scanf("%d%d", &u, &v) == 2);
g[u].push_back(v);
g[v].push_back(u);
}
return true;
}
vector<uli> ps[N];
inline uli getSum(int v, int l, int r) {
return ps[v][r] - ps[v][l];
}
const int MX = 700;
int id[N];
const int B = 1111;
bitset<N> has[B];
int szh = 0;
inline void solve() {
memset(id, -1, sizeof id);
szh = 0;
fore(v, 0, n) {
sort(g[v].begin(), g[v].end());
ps[v].assign(sz(g[v]) + 1, 0);
fore(i, 0, sz(g[v]))
ps[v][i + 1] = ps[v][i] + g[v][i];
if(sz(g[v]) >= MX) {
assert(szh < B);
id[v] = szh++;
for(int to : g[v])
has[id[v]][to] = 1;
}
}
uli all = 0;
fore(v, 0, n) {
uli lw = v, gr = n - v - 1;
all += a * v * (gr * (gr - 1) / 2);
all += b * v * (lw * gr);
all += c * v * (lw * (lw - 1) / 2);
}
uli sub1 = 0;
fore(v, 0, n) {
for(int to : g[v]) {
if(to > v)
break;
uli cnt = to;
uli sum = cnt * (cnt - 1) / 2;
sub1 += a * sum + cnt * (b * to + c * v);
cnt = v - to - 1;
sum = (2 * to + cnt + 1) * cnt / 2;
sub1 += b * sum + cnt * (a * to + c * v);
}
uli sum = 0;
fore(i, 0, sz(g[v])) {
if(g[v][i] > v)
break;
uli cnt = i;
sub1 -= a * sum + cnt * (b * g[v][i] + c * v);
sum += g[v][i];
}
}
all -= sub1;
uli sub2 = 0;
uli cntE = 0, sumE = 0;
fore(v, 0, n) {
sub2 += sumE + cntE * c * v;
for(int to : g[v]) {
if(to > v)
break;
cntE++;
sumE += a * to + b * v;
}
}
fore(v, 0, n) {
for(int to : g[v]) {
if(to > v)
break;
int pos = int(lower_bound(g[to].begin(), g[to].end(), to) - g[to].begin());
sub2 -= a * getSum(to, 0, pos) + pos * (b * to + c * v);
int pos2 = int(lower_bound(g[to].begin(), g[to].end(), v) - g[to].begin());
sub2 -= b * getSum(to, pos, pos2) + (pos2 - pos) * (a * to + c * v);
}
}
vector<char> curh(n + 5, 0);
fore(v, 0, n) {
if(id[v] == -1) {
fore(i2, 0, sz(g[v])) {
int u2 = g[v][i2];
if(u2 > v)
break;
if(id[u2] != -1) {
fore(i1, 0, i2) {
int u1 = g[v][i1];
if(has[id[u2]][u1])
sub2 += a * u1 + b * u2 + c * v;
}
} else {
for(int to : g[u2]) {
if(to > u2)
break;
curh[to] = 1;
}
fore(i1, 0, i2) {
int u1 = g[v][i1];
if(curh[u1])
sub2 += a * u1 + b * u2 + c * v;
}
for(int to : g[u2]) {
if(to > u2)
break;
curh[to] = 0;
}
}
}
} else {
fore(u2, 0, v) {
if(!has[id[v]][u2])
continue;
for(int u1 : g[u2]) {
if(u1 > u2)
break;
if(has[id[v]][u1])
sub2 += a * u1 + b * u2 + c * v;
}
}
}
}
all -= sub2;
cout << all << endl;
}
int main(){
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(10);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
#endif
}
return 0;
}