Snowlanuck

3755

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, m, A[N], B[N];

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> A[i];
for (int i = 1; i <= m; i ++) cin >> B[i];

for (int i = 1, j = 1; i <= n; i ++, j ++)
{
while (j <= m && B[j] != A[i]) j ++;
if (j > m) { puts("No"); return 0; }
}

puts("Yes");

return 0;
}


Snowlanuck
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const double eps = 1e-6;
int n, f;
double A[N], s[N];

bool check(double x)
{
for (int i = 1; i <= n; i ++)
s[i] = A[i] + s[i - 1] - x;
double mins = 0;
for (int i = f; i <= n; i ++)
{
mins = min(mins, s[i - f]);
if (s[i] >= mins) return true;
}
return false;
}

int main()
{
cin >> n >> f;

double l = 0, r = 0;
for (int i = 1; i <= n; i ++)
{
cin >> A[i];
r = max(r, A[i]);
}

while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}

cout << (int)(r * 1000);

return 0;
}


Snowlanuck
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 5e3 + 1;
int n, r, A[N + 10][N + 10];

int main()
{
cin >> n >> r;

int x, y, v;
while (n -- && cin >> x >> y >> v)
A[x + 1][y + 1] += v;

for (int i = 1; i < N; i ++)
for (int j = 1; j < N; j ++)
A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];

int ans = 0;
for (int i = 1; i < N; i ++)
for (int j = 1; j < N; j ++)
{
int nx = i + r - 1; if (nx >= N) nx = 5000;
int ny = j + r - 1; if (ny >= N) ny = 5000;
int v = A[nx][ny] - A[nx][j - 1] - A[i - 1][ny] + A[i - 1][j - 1];
//printf("%d %d, %d %d = %d\n", i, j, nx, ny, v);
ans = max(ans, v);
}

cout << ans;

return 0;
}


Snowlanuck
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 6, INF = 0x3f3f3f3f,
dx[5] = {0,0,1,-1,0},
dy[5] = {1,-1,0,0,0};
int n, A[N][N], B[N][N];

void turn(int x, int y)
{
for (int i = 0; i < 5; i ++)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > 5 || ny < 1 || ny > 5) continue;
B[nx][ny] = !B[nx][ny];
}
}

int main()
{
int T; cin >> T;
while (T --)
{
for (int i = 1; i <= 5; i ++)
for (int j = 1; j <= 5; j ++)
scanf("%1d", &A[i][j]);

int res = INF;
for (int i = 0; i < 32; i ++)
{
int cnt = 0;
memcpy(B, A, sizeof A);
for (int j = 0; j < 5; j ++)
if (!(i >> j & 1)) turn(1, j + 1), cnt ++;

for (int j = 1; j <= 4; j ++)
for (int k = 1; k <= 5; k ++)
if (!B[j][k]) turn(j + 1, k), cnt ++;

bool flag = true;
for (int j = 1; j <= 5; j ++)
for (int k = 1; k <= 5; k ++)
if (!B[j][k]) { flag = false; break; }

if (flag) res = min(res, cnt);
}

if (res > 6) res = -1;
cout << res << endl;
}

return 0;
}


Snowlanuck
1个月前
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

int main()
{
LL a, b, mod;
cin >> a >> b >> mod;

LL res = 0;

while (a)
{
if (a & 1) res = (res + b) % mod;
b = (b + b) % mod;
a >>= 1;
}

cout << res;

return 0;
}


Snowlanuck
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10, S = 55, M = 1e6 + 10;

int n, tr[N * S][26], cnt[N * S], idx;
int ne[N * S];

void insert(string str)
{
int p = 0;
for (int i = 0; i < str.size(); i ++)
{
int u = str[i] - 'a';
if (!tr[p][u]) tr[p][u] = ++ idx;
p = tr[p][u];
}
cnt[p] ++;
}

void build()
{
queue<int> q;
for (int i = 0; i < 26; i ++)
if (tr[0][i]) q.push(tr[0][i]);

while (q.size())
{
int u = q.front(); q.pop();
for (int i = 0; i < 26; i ++)
{
int p = tr[u][i];
if (!p) tr[u][i] = tr[ ne[u] ][i];
else
{
ne[p] = tr[ ne[u] ][i];
q.push(p);
}
}
}
}

int main()
{
int T; cin >> T;
while (T --)
{
memset(tr, 0, sizeof tr);
memset(cnt, 0, sizeof cnt);
memset(ne, 0, sizeof ne);
idx = 0;

cin >> n; string str;
for (int i = 0; i < n; i ++)
{
cin >> str;
insert(str);
}

build();
cin >> str;

int res = 0;
for (int i = 0, j = 0; i < str.size(); i ++)
{
int u = str[i] - 'a';
j = tr[j][u];

int p = j;
while (p)
{
res += cnt[p];
cnt[p] = 0;
p = ne[p];
}
}

cout << res << endl;
}

return 0;
}


Snowlanuck
1个月前
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
typedef long long LL;
set<int> s;

int main()
{
int n, x; cin >> n;

LL ans = 0; s.insert(-INF), s.insert(INF);
while (n -- && cin >> x)
{
if (s.size() == 2) ans += x, s.insert(x);
else
{
auto k = s.lower_bound(x);
if (*k != x)
{
auto a = k;
ans += min(abs(*(-- a) - x), abs(*k - x));
s.insert(x);
}
}
}

cout << ans;

return 0;
}


Snowlanuck
2个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n;
struct Node
{
int l, r;
int key, val;
int cnt, size;
}tr[N];

int root, idx;

void push_up(int u)
{
tr[u].size = tr[ tr[u].l ].size + tr[ tr[u].r ].size + tr[u].cnt;
}

int get_node(int key)
{
tr[ ++ idx ].key = key;
tr[idx].val = rand();
tr[idx].cnt = tr[idx].size = 1;
return idx;
}

void zig(int& u) //右旋
{
int p = tr[u].l;
tr[u].l = tr[p].r, tr[p].r = u, u = p;
push_up(tr[u].r), push_up(u);
}

void zag(int& u) //左旋
{
int p = tr[u].r;
tr[u].r = tr[p].l, tr[p].l = u, u = p;
push_up(tr[u].l), push_up(u);
}

void build()
{
get_node(-INF), get_node(INF);
root = 1, tr[1].r = 2;
push_up(root);

if (tr[1].val < tr[2].val) zag(root);
}

void insert(int& p, int key)
{
if (!p) p = get_node(key);
else if (tr[p].key == key) tr[p].cnt ++;
else if (tr[p].key > key)
{
insert(tr[p].l, key);
if (tr[ tr[p].l ].val > tr[p].val) zig(p);
}
else
{
insert(tr[p].r, key);
if (tr[ tr[p].r ].val > tr[p].val) zag(p);
}
push_up(p);
}

void remove(int& p, int key)
{
if (!p) return;
if (tr[p].key == key)
{
if (tr[p].cnt > 1) tr[p].cnt --;
else if (tr[p].l || tr[p].r)
{
if (!tr[p].r || tr[ tr[p].l ].val > tr[ tr[p].r ].val)
{
zig(p);
remove(tr[p].r, key);
}
else
{
zag(p);
remove(tr[p].l, key);
}
}
else p = 0;
}
else if (tr[p].key > key) remove(tr[p].l, key);
else remove(tr[p].r, key);

push_up(p);
}

int get_rank_by_key(int p, int key)
{
if (!p) return 0;
if (tr[p].key == key) return tr[ tr[p].l ].size + 1;
if (tr[p].key > key) return get_rank_by_key(tr[p].l, key);
return tr[ tr[p].l ].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}

int get_key_by_rank(int p, int rank)
{
if (!p) return INF;
if (tr[ tr[p].l ].size >= rank) return get_key_by_rank(tr[p].l, rank);
if (tr[ tr[p].l ].size + tr[p].cnt >= rank) return tr[p].key;
return get_key_by_rank(tr[p].r, rank - tr[ tr[p].l ].size - tr[p].cnt);
}

int get_prev(int p, int key)
{
if (!p) return -INF;
if (tr[p].key >= key) return get_prev(tr[p].l, key);
return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int p, int key)
{
if (!p) return INF;
if (tr[p].key <= key) return get_next(tr[p].r, key);
return min(tr[p].key, get_next(tr[p].l, key));
}

int main()
{
build();

cin >> n;
int op, x;
while (n -- && cin >> op >> x)
{
if (op == 1) insert(root, x);
else if (op == 2) remove(root, x);
else if (op == 3) cout << (get_rank_by_key(root, x) - 1) << endl;
else if (op == 4) cout << get_key_by_rank(root, x + 1) << endl;
else if (op == 5) cout << get_prev(root, x) << endl;
else cout << get_next(root, x) << endl;
}

return 0;
}


Snowlanuck
2个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 1e4 + 10;
int n, m, A[N];
vector<int> nums;

struct Node{int l, r, cnt;}tr[N * 4 + N * 17];
int root[N], idx;

int find(int x)
{
return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

int build(int l, int r)
{
int p = ++ idx;
if (l == r) return p;
int mid = l + r >> 1;
tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
return p;
}

int insert(int p, int l, int r, int x)
{
int q = ++ idx;
tr[q] = tr[p];
if (l == r) { tr[q].cnt ++; return q; }
int mid = l + r >> 1;
if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
else tr[q].r = insert(tr[p].r, mid + 1, r, x);
tr[q].cnt = tr[ tr[q].l ].cnt + tr[ tr[q].r ].cnt;
return q;

}

int query(int q, int p, int l, int r, int k)
{
if (l == r) return r;
int cnt = tr[ tr[q].l ].cnt - tr[ tr[p].l ].cnt;
int mid = l + r >> 1;
if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
cin >> A[i];
nums.push_back(A[i]);
}

sort(nums.begin(), nums.end());
nums.erase( unique(nums.begin(), nums.end()), nums.end() );

root[0] = build(0, nums.size() - 1);

for (int i = 1; i <= n; i ++)
root[i] = insert(root[i - 1], 0, nums.size() - 1, find(A[i]));

int l, r, k;
while (m -- && cin >> l >> r >> k)
cout << nums[ query(root[r], root[l - 1], 0, nums.size() - 1, k) ] << endl;

return 0;
}


Snowlanuck
2个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
struct Segment
{
double x, y1, y2;
int k;
}seg[N * 2];

struct Node
{
int l, r, cnt;
double len;
}tr[N * 8];

int n;
vector<double> ys;

int find(double y)
{
return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

void push_up(int u)
{
if (tr[u].cnt) tr[u].len = ys[ tr[u].r + 1 ] - ys[ tr[u].l ];
else if (tr[u].l != tr[u].r) tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
else tr[u].len = 0;
}

void build(int u, int l, int r)
{
tr[u] = {l, r, 0, 0};
if (l != r)
{
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
}

void modify(int u, int l, int r, int k)
{
if (tr[u].l >= l && tr[u].r <= r)
{
tr[u].cnt += k;
push_up(u);
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, k);
if (r > mid) modify(u << 1 | 1, l, r, k);
push_up(u);
}
}

int main()
{
int T = 1;
while (cin >> n && n)
{
ys.clear();
for (int i = 0, j = 0; i < n; i ++)
{
double x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
seg[j ++] = {x1, y1, y2, 1};
seg[j ++] = {x2, y1, y2, -1};
ys.push_back(y1), ys.push_back(y2);
}

sort(ys.begin(), ys.end());
ys.erase( unique(ys.begin(), ys.end()), ys.end() );

build(1, 0, ys.size() - 2);

sort(seg, seg + n * 2, [](Segment A, Segment B){ return A.x < B.x; });

double res = 0;
for (int i = 0; i < n * 2; i ++)
{
if (i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);
modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
}

printf("Test case #%d\n", T ++);
printf("Total explored area: %.2lf\n\n", res);
}

return 0;
}