Skip to content

Instantly share code, notes, and snippets.

@MinecraftFuns

MinecraftFuns/README.md

Last active June 8, 2021 09:10
Show Gist options
  • Save MinecraftFuns/706d87a84abcdb36534820a7a8709609 to your computer and use it in GitHub Desktop.
Save MinecraftFuns/706d87a84abcdb36534820a7a8709609 to your computer and use it in GitHub Desktop.
Download ZIP
CF930 / Codeforces Round 468 (Div. 1)
Raw
a.cpp
#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
<< (#x) << ": " << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename Tp>
inline void read(Tp &x)
{
static char c;
static bool neg;
x = 0, c = getchar(), neg = false;
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = true;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
const int N = 100000 + 5;
int n;
int dep[N], cnt[N];
int main()
{
read(n);
dep[1] = 1;
++cnt[1];
for (int v = 2, u; v <= n; ++v)
{
read(u);
dep[v] = dep[u] + 1;
++cnt[dep[v]];
}
int ans = 0;
for (int i = 1; i <= n; ++i)
{
ans += cnt[i] % 2;
}
printf("%d\n", ans);
}
Raw
b.cpp
#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
<< (#x) << ": " << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename Tp>
inline void read(Tp &x)
{
static char c;
static bool neg;
x = 0, c = getchar(), neg = false;
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = true;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
const int N = 5000 + 5;
const int CS = 26;
char str[N * 2];
vector<int> pos[CS];
int buc[CS];
int main()
{
scanf("%s", str);
int n = strlen(str), ans = 0;
for (int i = 0; i < n; ++i)
{
pos[str[i] - 'a'].emplace_back(i);
}
copy(str, str + n, str + n);
for (int i = 0, now, cnt; i < CS; ++i)
{
now = 0;
for (int d = 1; d < n; ++d)
{
memset(buc, 0, sizeof(buc));
for (const auto &v : pos[i])
{
++buc[str[v + d] - 'a'];
}
cnt = 0;
for (int i = 0; i < CS; ++i)
{
cnt += (buc[i] == 1);
}
now = std::max(now, cnt);
}
ans += now;
}
printf("%.8f\n", (double)ans / (double)n);
}
Raw
c.cpp
#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
<< (#x) << ": " << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename Tp>
inline void read(Tp &x)
{
static char c;
static bool neg;
x = 0, c = getchar(), neg = false;
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = true;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
const int N = 100000 + 5;
int n, m;
int line[N];
int f[N], g[N];
namespace BIT
{
#define lowbit(x) ((x) & -(x))
int t[N];
inline void clear()
{
memset(t, 0, sizeof(t));
}
inline void add(int x, int val)
{
for (; x < N; x += lowbit(x))
{
t[x] = std::max(t[x], val);
}
}
inline int query(int x)
{
int res = 0;
for (; x > 0; x -= lowbit(x))
{
res = std::max(res, t[x]);
}
return res;
}
#undef lowbit
} // namespace BIT
int main()
{
read(n), read(m);
for (int i = 1, l, r; i <= n; ++i)
{
read(l), read(r);
++line[l], --line[r + 1];
}
++line[1];
for (int i = 1; i <= m; ++i)
{
line[i] += line[i - 1];
}
for (int i = 1; i <= m; ++i)
{
f[i] = BIT::query(line[i]) + 1;
BIT::add(line[i], f[i]);
}
BIT::clear();
for (int i = m; i >= 1; --i)
{
g[i] = BIT::query(line[i]) + 1;
BIT::add(line[i], g[i]);
}
int ans = 0;
for (int i = 1; i <= m; ++i)
{
ans = std::max(ans, f[i] + g[i] - 1);
}
printf("%d\n", ans);
return 0;
}
Raw
d.cpp
#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
<< (#x) << ": " << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename Tp>
inline void read(Tp &x)
{
static char c;
static bool neg;
x = 0, c = getchar(), neg = false;
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = true;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
const int MX = 1e5 + 2;
const int ADD = MX * 2;
const int N = ADD * 2;
const int SET = 0x3f;
int n;
vector<pii> vec[2];
ll ans;
int upL[N], upR[N], downL[N], downR[N];
template <typename Tp>
inline void checkMax(Tp &x, const Tp &y)
{
if (x < y)
{
x = y;
}
}
template <typename Tp>
inline void checkMin(Tp &x, const Tp &y)
{
if (x > y)
{
x = y;
}
}
inline void work(const vector<pii> &points)
{
memset(upL, -SET, sizeof(upL));
memset(downL, SET, sizeof(downL));
for (const auto &p : points)
{
checkMax(upL[p.first], p.second);
checkMin(downL[p.first], p.second);
}
memcpy(upR, upL, sizeof(upL));
memcpy(downR, downL, sizeof(downL));
for (int i = 1; i < N; ++i)
{
checkMax(upL[i], upL[i - 1]);
checkMin(downL[i], downL[i - 1]);
}
for (int i = N - 2; i >= 0; --i)
{
checkMax(upR[i], upR[i + 1]);
checkMin(downR[i], downR[i + 1]);
}
for (int i = 1, up, down; i < N; i += 2)
{
up = std::min(upL[i], upR[i]);
down = std::max(downL[i], downR[i]);
if (up > down)
{
ans += (up - down) / 2;
}
}
}
int main()
{
read(n);
vec[0].reserve(n);
vec[1].reserve(n);
for (int i = 1, x, y, b; i <= n; ++i)
{
read(x), read(y);
b = (x + y + ADD) % 2;
vec[b].emplace_back((pii){x + y + ADD + b, x - y + ADD + b});
}
work(vec[0]);
work(vec[1]);
std::printf("%lld\n", ans);
}
Raw
d.ref.cpp
#include <bits/stdc++.h>
#define LL long long
#define LD long double
#define ull unsigned long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
#define fio \
ios::sync_with_stdio(false); \
cin.tie(0);
using namespace std;
const int N = 4e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
const double PI = acos(-1);
template <class T, class S>
inline void add(T &a, S b)
{
a += b;
if (a >= mod)
a -= mod;
}
template <class T, class S>
inline void sub(T &a, S b)
{
a -= b;
if (a < 0)
a += mod;
}
template <class T, class S>
inline bool chkmax(T &a, S b) { return a < b ? a = b, true : false; }
template <class T, class S>
inline bool chkmin(T &a, S b) { return a > b ? a = b, true : false; }
const int B = 200001;
int n;
vector<PII> v[2];
int upL[N], dnL[N];
int upR[N], dnR[N];
LL solve(vector<PII> &v)
{
memset(upL, 0xc0, sizeof(upL));
memset(dnL, 0x3f, sizeof(dnL));
memset(upR, 0xc0, sizeof(upR));
memset(dnR, 0x3f, sizeof(dnR));
for (auto &t : v)
{
chkmax(upL[t.fi], t.se);
chkmin(dnL[t.fi], t.se);
chkmax(upR[t.fi], t.se);
chkmin(dnR[t.fi], t.se);
}
for (int i = 1; i < N; i++)
{
chkmax(upL[i], upL[i - 1]);
chkmin(dnL[i], dnL[i - 1]);
}
for (int i = N - 2; i >= 1; i--)
{
chkmax(upR[i], upR[i + 1]);
chkmin(dnR[i], dnR[i + 1]);
}
LL ans = 0;
for (int i = 1; i < N - 1; i += 2)
{
int up = min(upL[i], upR[i]);
int dn = max(dnL[i], dnR[i]);
if (up > dn)
ans += (up - dn) / 2;
}
return ans;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
int z = (x + y + B) & 1;
v[z].push_back(mk(x + y + B + z, x - y + B + z));
}
LL ans = 0;
ans += solve(v[0]);
ans += solve(v[1]);
printf("%lld\n", ans);
return 0;
}
/*
*/
Raw
e.cpp
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
<< (#x) << ": " << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename Tp>
inline void read(Tp &x)
{
static char c;
static bool neg;
x = 0, c = getchar(), neg = false;
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = true;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
const int N = 1e5 + 5;
const int MX = N * 4;
const int MOD = 1e9 + 7;
int k, n, m;
int l0[N], r0[N], l1[N], r1[N];
int min0[MX], min1[MX], f[MX][2], g[MX];
int discrete[MX];
inline int mul(const int &x, const int &y)
{
int res = (ll)x * y % MOD;
if (res < 0)
{
res += MOD;
}
return res;
}
inline int power(int base, int exp)
{
int res = 1;
while (exp > 0)
{
if (exp & 1)
{
res = mul(res, base);
}
base = mul(base, base);
exp >>= 1;
}
return res;
}
inline int sum(const int &x, const int &y)
{
int res = x + y;
if (res >= MOD)
{
res -= MOD;
}
else if (res < 0)
{
res += MOD;
}
return res;
}
inline int sum(const initializer_list<int> &ls)
{
int res = 0;
for (const auto &x : ls)
{
res = sum(res, x);
}
return res;
}
int main()
{
read(k), read(n), read(m);
for (int i = 1; i <= n; ++i)
{
read(l0[i]), read(r0[i]);
--l0[i];
}
copy(l0 + 1, l0 + n + 1, discrete + 1);
int lim = n;
copy(r0 + 1, r0 + n + 1, discrete + lim + 1);
lim += n;
for (int i = 1; i <= m; ++i)
{
read(l1[i]), read(r1[i]);
--l1[i];
}
copy(l1 + 1, l1 + m + 1, discrete + lim + 1);
lim += m;
copy(r1 + 1, r1 + m + 1, discrete + lim + 1);
lim += m;
discrete[++lim] = k;
sort(discrete, discrete + lim + 1);
lim = unique(discrete, discrete + lim + 1) - discrete - 1;
fill(min0, min0 + lim + 1, lim + 1);
fill(min1, min1 + lim + 1, lim + 1);
for (int i = 1; i <= n; ++i)
{
l0[i] = lower_bound(discrete, discrete + lim + 1, l0[i]) - discrete;
r0[i] = lower_bound(discrete, discrete + lim + 1, r0[i]) - discrete;
min0[l0[i]] = std::min(min0[l0[i]], r0[i]);
}
for (int i = 1; i <= m; ++i)
{
l1[i] = lower_bound(discrete, discrete + lim + 1, l1[i]) - discrete;
r1[i] = lower_bound(discrete, discrete + lim + 1, r1[i]) - discrete;
min1[l1[i]] = std::min(min1[l1[i]], r1[i]);
}
for (int i = lim; i >= 1; --i)
{
min0[i - 1] = std::min(min0[i], min0[i - 1]);
min1[i - 1] = std::min(min1[i], min1[i - 1]);
}
f[lim][0] = f[lim][1] = g[lim] = 1;
for (int i = lim - 1, g0, g1, g2; i >= 0; --i)
{
g0 = sum(f[i + 1][0], -f[min0[i]][0]);
g1 = sum(f[i + 1][1], -f[min1[i]][1]);
g2 = mul(g[i + 1], sum(power(2, sum(discrete[i + 1], -discrete[i])), -2));
f[i][0] = sum({f[i + 1][0], g1, g2});
f[i][1] = sum({f[i + 1][1], g0, g2});
g[i] = sum({g0, g1, g2});
}
printf("%d\n", g[0]);
}
Raw
e.pai.cpp
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
inline int getint()
{
char ch;
while (!isdigit(ch = getchar()))
;
int x = ch ^ '0';
while (isdigit(ch = getchar()))
x = (((x << 2) + x) << 1) + (ch ^ '0');
return x;
}
constexpr int N = 1e5, mod = 1e9 + 7;
std::pair<int, int> p[2][N];
int tmp[N * 4 + 2], Min[2][N * 4 + 2], f[N * 4 + 2][3];
inline int power(int a, int k)
{
int ret = 1;
for (; k; k >>= 1)
{
if (k & 1)
ret = (int64)ret * a % mod;
a = (int64)a * a % mod;
}
return ret;
}
int main()
{
const int k = getint(), n = getint(), m = getint();
int lim = 0;
for (int i = 0; i < n; i++)
{
tmp[++lim] = p[0][i].first = getint() - 1;
tmp[++lim] = p[0][i].second = getint();
}
for (int i = 0; i < m; i++)
{
tmp[++lim] = p[1][i].first = getint() - 1;
tmp[++lim] = p[1][i].second = getint();
}
tmp[++lim] = k;
assert(lim == n * 2 + m * 2 + 1);
std::sort(&tmp[0], &tmp[lim] + 1);
for (int i = 0; i <= lim; ++i)
{
cout << tmp[i] << " ";
}
cout << endl
<< endl;
lim = std::unique(&tmp[0], &tmp[lim] + 1) - &tmp[1];
for (int i = 0; i <= lim; i++)
{
Min[0][i] = Min[1][i] = lim + 1;
}
for (int i = 0; i < n; i++)
{
p[0][i].first = std::lower_bound(&tmp[0], &tmp[lim] + 1, p[0][i].first) - tmp;
p[0][i].second = std::lower_bound(&tmp[0], &tmp[lim] + 1, p[0][i].second) - tmp;
Min[0][p[0][i].first] = std::min(Min[0][p[0][i].first], p[0][i].second);
}
for (int i = 0; i < m; i++)
{
p[1][i].first = std::lower_bound(&tmp[0], &tmp[lim] + 1, p[1][i].first) - tmp;
p[1][i].second = std::lower_bound(&tmp[0], &tmp[lim] + 1, p[1][i].second) - tmp;
Min[1][p[1][i].first] = std::min(Min[1][p[1][i].first], p[1][i].second);
}
for (int i = lim; i; i--)
{
Min[0][i - 1] = std::min(Min[0][i - 1], Min[0][i]);
Min[1][i - 1] = std::min(Min[1][i - 1], Min[1][i]);
}
f[lim][0] = f[lim][1] = f[lim][2] = 1;
for (int i = lim - 1; i >= 0; i--)
{
int g[3];
g[0] = (f[i + 1][0] - f[Min[0][i]][0] + mod) % mod;
g[1] = (f[i + 1][1] - f[Min[1][i]][1] + mod) % mod;
g[2] = (int64)f[i + 1][2] * ((power(2, tmp[i + 1] - tmp[i]) - 2 + mod) % mod) % mod;
cout << g[0] << " " << g[1] << " " << g[2] << endl;
f[i][0] = ((int64)f[i + 1][0] + g[1] + g[2]) % mod;
f[i][1] = ((int64)f[i + 1][1] + g[0] + g[2]) % mod;
f[i][2] = ((int64)g[0] + g[1] + g[2]) % mod;
}
printf("%d\n", f[0][2]);
return 0;
}
Raw
e.rainair.cpp
#include <bits/stdc++.h>
typedef std::pair<int, int> P;
typedef long long LL;
#define MP std::make_pair
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 5e5 + 5;
const int ha = 1e9 + 7;
std::vector<int> S;
int k, m0, m1, n;
P a[2][MAXN];
int lim[2][MAXN];
int f[2][MAXN];
// int f[2][105][105];
inline int qpow(int a, int n = ha - 2)
{
int res = 1;
while (n)
{
if (n & 1)
res = 1ll * res * a % ha;
a = 1ll * a * a % ha;
n >>= 1;
}
return res;
}
inline void add(int &x, int y)
{
x += y;
if (x >= ha)
x -= ha;
}
int main()
{
scanf("%d%d%d", &k, &m0, &m1);
for (int i = 1; i <= m0; ++i)
{
scanf("%d%d", &a[0][i].first, &a[0][i].second);
S.push_back(a[0][i].first - 1);
S.push_back(a[0][i].second);
}
for (int i = 1; i <= m1; ++i)
{
scanf("%d%d", &a[1][i].first, &a[1][i].second);
S.push_back(a[1][i].first - 1);
S.push_back(a[1][i].second);
}
S.push_back(0);
S.push_back(k);
std::sort(all(S));
S.erase(std::unique(all(S)), S.end());
CLR(lim, -1);
for (int i = 1; i <= m0; ++i)
{
a[0][i].first = std::lower_bound(all(S), a[0][i].first - 1) - S.begin();
a[0][i].second = std::lower_bound(all(S), a[0][i].second) - S.begin();
lim[0][a[0][i].second] = std::max(lim[0][a[0][i].second], a[0][i].first);
}
for (int i = 1; i <= m1; ++i)
{
a[1][i].first = std::lower_bound(all(S), a[1][i].first - 1) - S.begin();
a[1][i].second = std::lower_bound(all(S), a[1][i].second) - S.begin();
lim[1][a[1][i].second] = std::max(lim[1][a[1][i].second], a[1][i].first);
}
n = S.size();
for (int i = 0; i <= 1; ++i)
for (int j = 1; j <= n; ++j)
lim[i][j] = std::max(lim[i][j], lim[i][j - 1]);
f[0][0] = 1;
int sm0 = 1, tp0 = 0, sm1 = 0, tp1 = 0;
for (int i = 0; i <= n - 2; ++i)
{
while (tp0 <= lim[1][i])
add(sm0, ha - f[0][tp0]), tp0++;
while (tp1 <= lim[0][i])
add(sm1, ha - f[1][tp1]), tp1++;
int gx = (qpow(2, S[i + 1] - S[i] - 1) + ha - 1) % ha;
gx = 1ll * gx * (sm0 + sm1) % ha;
add(f[0][i + 1], gx);
add(f[1][i + 1], gx);
add(f[0][i], sm1);
add(f[1][i], sm0);
int t0 = sm0, t1 = sm1;
add(sm0, gx);
add(sm1, gx);
add(sm0, t1);
add(sm1, t0);
}
// f[0][0][0] = 1;
// FOR(i,0,n-2){
// FOR(j,0,i){
// if(j > lim[1][i]){
// add(f[0][i+1][j],f[0][i][j]);
// add(f[1][i+1][i],f[0][i][j]);
// int gx = (qpow(2,S[i+1]-S[i]-1)+ha-1)%ha;
// gx = 1ll*gx*f[0][i][j]%ha;
// add(f[0][i+1][i+1],gx);
// add(f[1][i+1][i+1],gx);
// }
// else f[0][i][j] = 0;
// if(j > lim[0][i]){
// add(f[1][i+1][j],f[1][i][j]);
// add(f[0][i+1][i],f[1][i][j]);
// int gx = (qpow(2,S[i+1]-S[i]-1)+ha-1)%ha;
// gx = 1ll*gx*f[1][i][j]%ha;
// add(f[1][i+1][i+1],gx);
// add(f[0][i+1][i+1],gx);
// }
// else f[1][i][j] = 0;
// }
// }
// 1 2 3 5
// DEBUG(f[0][4][4]);DEBUG(f[0][4][3]);
int ans = 0;
for (int i = 0; i <= n; ++i)
if (i > lim[1][n])
add(ans, f[0][i]);
for (int i = 0; i <= n; ++i)
if (i > lim[0][n])
add(ans, f[1][i]);
printf("%d\n", ans);
// DEBUG(ans);
return 0;
}
/*
f[0/1][i][j] 表示考虑到第i个点,上一个和这个点颜色不同的地方是j
定义 i 所在的块是 (x[i-1],x[i]]
pre 表示前面最远的哪一个块必须有0/1
f[0][i][j] -> f[0][i+1][j](pre[1][i+1] <= j)
f[0][i][j] -> f[1][i+1][i](pre[0][i+1] <= j)
(2^{x[i+1]-x[i]-1}-1)f[0][i][j] -> f[0][i+1][i+1]\f[1][i+1][i+1](pre[1][i+1] <= j\pre[0][i+1] <= j)
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment