| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1282169 | iamhereforfun | Teams (IOI15_teams) | C++20 | 0 ms | 0 KiB |
// Starcraft 2 enjoyer //
#include <bits/stdc++.h>
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 1e5 + 5;
const int M = 21e4 + 5;
const int LG = 31;
const int C = 26;
const int INF = 1e9 + 5;
const int P = 31;
const int MOD = 1e9 + 7;
struct PersistentSegmentTree
{
struct Node
{
int sum;
Node *le, *ri;
int val(Node *cur)
{
return cur ? cur->sum : 0;
}
Node(int i)
{
sum = i;
le = ri = NULL;
}
Node(Node *cur)
{
if (!cur)
{
sum = 0;
return;
}
sum = cur->sum;
le = cur->le;
ri = cur->ri;
}
Node(Node *l, Node *r)
{
sum = val(l) + val(r);
le = l;
ri = r;
}
} *root[N];
int n;
Node *build(int l, int r)
{
if (l == r)
{
return new Node(0);
}
else
{
int m = (l + r) / 2;
return new Node(build(l, m), build(m + 1, r));
}
}
Node *update(Node *cur, int v, int p, int l, int r)
{
if (l == r)
{
return new Node(v + cur->sum);
}
else
{
int m = (l + r) / 2;
if (p <= m)
{
return new Node(update(cur->le, v, p, l, m), cur->ri);
}
else
{
return new Node(cur->le, update(cur->ri, v, p, m + 1, r));
}
}
}
int get(Node *cur, int l, int r, int tl, int tr)
{
if (tl > tr)
return 0;
if (tl <= l && r <= tr)
{
return cur->sum;
}
else
{
int m = (l + r) / 2;
return get(cur->le, l, m, tl, min(tr, m)) + get(cur->ri, m + 1, r, max(tl, m + 1), tr);
}
}
PersistentSegmentTree(int n) : n(n) { root[0] = build(0, n - 1); };
void add(int i, int j)
{
root[j] = new Node(root[i]);
}
void update(int i, int v, int p)
{
root[i] = update(root[i], v, p, 0, n - 1);
}
int get(int i, int l, int r)
{
if (l > r)
return 0;
return get(root[i], 0, n - 1, l, r);
}
} pst(N);
int n, q, a[N], b[N], k[N], last, offset;
pair<int, int> rng[N];
int can(int m, int k[])
{
last = 0;
offset = 0;
sort(k, k + m);
for (int x = 0; x < m; x++)
{
if (k[x] > last)
{
last = k[x];
offset = 0;
}
int l = last, r = n, ans = -1;
cout << k[x] << " " << offset << "v\n";
cout << pst.get(k[x], last, n) + offset << "w\n";
while (l <= r)
{
int m = (l + r) / 2;
if (pst.get(k[x], last, m) + offset < k[x])
{
l = m + 1;
}
else
{
ans = m;
r = m - 1;
}
}
cout << offset << " " << ans << "\n";
if (ans == -1)
{
last = -1;
break;
}
else
{
int i = k[x] - (pst.get(k[x], last, ans - 1) + offset);
offset = -i;
}
last = ans;
}
if (last == -1)
return 0;
else
return 1;
}
void solve()
{
cin >> n;
for (int x = 1; x <= n; x++)
{
cin >> a[x] >> b[x];
rng[x] = {a[x], b[x]};
}
sort(rng + 1, rng + n + 1);
last = 0;
for (int x = 1; x <= n; x++)
{
auto &[l, r] = rng[x];
while (last < l)
{
pst.add(last, last + 1);
last++;
}
pst.update(last, 1, r);
}
for (int x = last; x <= n; x++)
{
pst.add(x, x + 1);
}
cin >> q;
for (int x = 0; x < q; x++)
{
int m;
cin >> m;
for (int y = 0; y < m; y++)
{
cin >> k[y];
}
cout << can(m, k) << "\n";
}
}
signed main()
{
freopen("CP.INP", "r", stdin);
freopen("CP.OUT", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
for (int x = 1; x <= t; x++)
{
solve();
}
return 0;
}