Created
December 6, 2020 10:43
-
-
Save sbsatter/75274f4d6369d6225fc3737f3d954505 to your computer and use it in GitHub Desktop.
Solution to Supercomputer using segment tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // | |
| // supercomputer.cpp | |
| // Competitive Programming | |
| // | |
| // Created by Shahed Bin Satter on 25/9/20. | |
| // Copyright © 2020 Shahed Bin Satter. All rights reserved. | |
| // | |
| #include <iostream> | |
| using namespace std; | |
| const int nmax = 1e5 + 1; | |
| int tree [nmax * 4]; | |
| int arr [nmax]; | |
| void build(int id, int l, int r) { | |
| if (l == r) { | |
| tree[id] = 1; | |
| return; | |
| } | |
| int mid = (l + r) / 2; | |
| build(2 * id, l, mid); | |
| build(2 * id + 1, mid + 1, r); | |
| tree[id] = tree[2 * id] + tree[2 * id + 1]; | |
| } | |
| void update(int id, int left, int right, int idx) { | |
| if (left == right) { | |
| tree[id] = 0; | |
| return; | |
| } | |
| int mid = (left + right) / 2; | |
| if (idx <= mid) { | |
| update(2 * id, left, mid, idx); | |
| } else { | |
| update(2 * id + 1, mid + 1, right, idx); | |
| } | |
| tree[id] = tree[id * 2] + tree[id * 2 + 1]; | |
| } | |
| int query(int id, int left, int right, int a, int b) { | |
| if (left > b || right < a) { | |
| return 0; | |
| } | |
| if (left >= a && right <= b) { | |
| return tree[id]; | |
| } | |
| int mid = (left + right) / 2; | |
| int l = query(2 * id, left, mid, a, b); | |
| int r = query(2 * id + 1, mid + 1, right, a, b); | |
| return l + r; | |
| } | |
| int main() { | |
| ios::sync_with_stdio(false); | |
| cin.tie(NULL); | |
| cout.tie(NULL); | |
| int n; | |
| cin >> n; | |
| for (int i = 1; i <= n; i++) { | |
| int x; | |
| cin >> x; | |
| arr[x] = i; | |
| } | |
| build(1, 1, n); | |
| int y = 0; | |
| for (int i = 1; i <= n; i++) { | |
| if (i % 2 == 0) { | |
| // even | |
| int x = n - y; | |
| cout << query(1, 1, n, 1, n) - query(1, 1, n, 1, arr[x]) << "\n"; | |
| update(1, 1, n, arr[x]); | |
| y++; | |
| } else { | |
| // odd | |
| int x = 1 + y; | |
| cout << query(1, 1, n, 1, arr[x] - 1) << "\n"; | |
| update(1, 1, n, arr[x]); | |
| } | |
| } | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment