QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #187801 | #7108. Couleur | UrgantTeam# | RE | 0ms | 12840kb | C++23 | 4.4kb | 2023-09-24 23:03:57 | 2023-09-24 23:03:57 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
typedef tree <pair <int, int>, null_type, less <pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int mas[100005];
set <pair <int, int> > left_bounds;
set <pair <ll, int> > inv;
int quant = 0;
pair <int, int> segments[100005];
ll inversions[100005];
ordered_set sort_ord[100005];
ll get_answer(int n)
{
return (*inv.rbegin()).x;
}
void update(int pos, int n)
{
int num = (*prev(left_bounds.upper_bound(mp(pos, n + 1)))).y;
left_bounds.erase(mp(segments[num].x, num));
inv.erase(mp(inversions[num], num));
if (segments[num].x == segments[num].y) return;
if (pos == segments[num].x)
{
sort_ord[num].erase(mp(mas[pos], pos));
inversions[num] -= sort_ord[num].order_of_key(mp(mas[pos], pos));
inv.insert(mp(inversions[num], num));
segments[num].x++;
left_bounds.insert(mp(segments[num].x, num));
return;
}
if (pos == segments[num].y)
{
sort_ord[num].erase(mp(mas[pos], pos));
inversions[num] -= ((int) sort_ord[num].size() - sort_ord[num].order_of_key(mp(mas[pos], pos)));
inv.insert(mp(inversions[num], num));
segments[num].y--;
left_bounds.insert(mp(segments[num].x, num));
return;
}
int lef_seg = num, rig_seg = num;
sort_ord[num].erase(mp(mas[pos], pos));
++quant;
sort_ord[quant].clear();
inversions[quant] = 0;
if (pos - segments[num].x <= segments[num].y - pos)
{
lef_seg = quant;
for (int i = pos - 1; i >= segments[num].x; i--)
{
sort_ord[rig_seg].erase(mp(mas[i], i));
inversions[lef_seg] += sort_ord[lef_seg].order_of_key(mp(mas[i], i));
sort_ord[lef_seg].insert(mp(mas[i], i));
}
inversions[rig_seg] -= inversions[lef_seg];
for (int i = pos - 1; i >= segments[num].x; i--)
{
inversions[rig_seg] -= sort_ord[rig_seg].order_of_key(mp(mas[i], i));
}
inversions[rig_seg] -= ((int) sort_ord[lef_seg].size() - sort_ord[lef_seg].order_of_key(mp(mas[pos], pos))) +
sort_ord[rig_seg].order_of_key(mp(mas[pos], pos));
}
else
{
rig_seg = quant;
for (int i = segments[num].y; i > pos; i--)
{
sort_ord[lef_seg].erase(mp(mas[i], i));
inversions[rig_seg] += sort_ord[rig_seg].order_of_key(mp(mas[i], i));
sort_ord[rig_seg].insert(mp(mas[i], i));
}
inversions[lef_seg] -= inversions[rig_seg];
for (int i = segments[num].y; i > pos; i--)
{
inversions[lef_seg] -= ((int) sort_ord[lef_seg].size() - sort_ord[lef_seg].order_of_key(mp(mas[i], i)));
}
inversions[lef_seg] -= ((int) sort_ord[lef_seg].size() - sort_ord[lef_seg].order_of_key(mp(mas[pos], pos))) +
sort_ord[rig_seg].order_of_key(mp(mas[pos], pos));
}
segments[lef_seg] = mp(segments[num].x, pos - 1);
segments[rig_seg] = mp(pos + 1, segments[num].y);
left_bounds.insert(mp(segments[lef_seg].x, lef_seg));
left_bounds.insert(mp(segments[rig_seg].x, rig_seg));
inv.insert(mp(inversions[lef_seg], lef_seg));
inv.insert(mp(inversions[rig_seg], rig_seg));
return;
}
ll calc_inversion(int n)
{
ll ans = 0;
for (int i = n; i >= 1; i--)
{
ans += sort_ord[quant].order_of_key(mp(mas[i], i));
sort_ord[quant].insert(mp(mas[i], i));
}
return ans;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int test;
cin >> test;
for (int rep = 1; rep <= test; rep++)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> mas[i];
left_bounds.clear();
inv.clear();
quant = 0;
left_bounds.insert(mp(1, ++quant));
segments[quant] = mp(1, n);
sort_ord[quant].clear();
inversions[quant] = calc_inversion(n);
inv.insert(mp(inversions[quant], quant));
for (int i = 1; i <= n; i++)
{
ll nxt;
cin >> nxt;
ll ans = get_answer(n);
cout << ans;
if (i != n) cout << ' ';
else cout << '\n';
nxt ^= ans;
update(nxt, n);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12840kb
input:
3 5 4 3 1 1 1 5 4 5 3 1 10 9 7 1 4 7 8 5 7 4 8 21 8 15 5 9 2 4 5 10 6 15 4 8 8 1 12 1 10 14 7 14 2 9 13 10 3 37 19 23 15 7 2 10 15 2 13 4 5 8 7 10
output:
7 0 0 0 0 20 11 7 2 0 0 0 0 0 0 42 31 21 14 14 4 1 1 1 0 0 0 0 0 0
result:
ok 3 lines
Test #2:
score: -100
Runtime Error
input:
11116 10 10 5 10 3 6 4 8 5 9 8 31 27 24 11 12 3 0 2 3 1 10 8 2 7 2 8 10 1 10 9 10 6 5 2 13 2 1 0 1 3 1 10 7 10 7 6 1 3 10 6 7 9 21 18 10 1 6 5 4 8 9 10 10 2 10 4 8 8 5 7 2 6 7 20 10 9 1 15 0 4 2 9 7 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10 6 3 5 2 7 10 9 1 4 8 10 1 10 1 3...
output:
21 18 16 12 10 6 4 1 1 0 12 12 10 10 4 4 4 2 1 0 20 16 9 5 3 3 3 0 0 0 22 14 8 8 5 5 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19 12 7 4 4 2 2 1 0 0 20 18 8 3 1 1 0 0 0 0 45 21 21 10 3 3 3 0 0 0 17 11 8 2 1 1 1 0 0 0 13 4 1 0 0 0 0 0 0 0 29 27 22 15 9 7 4 3 1 0 26 16 9 2 1 1 1 1 1 0 0 0 0 0 0 ...