oj.uz

Submission #504080

# Submission time Handle Problem Language Result Execution time Memory
504080 2022-01-09T17:02:12 Z hoanghq2004 Index (COCI21_index) C++14
110 / 110
 329 ms 34868 KB 
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 10;

int n, q;
int ans[N], BIT[N], h[N];
vector <int> p[N];

struct dta {
    int L, R, i;
};

void add(int i, int delta) {
    for (; i <= n; i += i & - i) BIT[i] += delta;
}

int get(int i) {
    int ans = 0;
    for (; i; i -= i & - i) ans += BIT[i];
    return ans;
}

void solve(int L, int R, vector <dta>& task) {
    if (task.empty()) return;
    if (L == R) {
        for (auto [u, v, i]: task) ans[i] = L;
        return;
    }
    int mid = L + R >> 1;
    for (int i = R; i > mid; --i)
        for (auto id: p[i]) add(id, 1);
    vector <dta> p1, p2;
    for (auto [u, v, i]: task) {
        if (get(v) - get(u - 1) >= mid + 1) p2.push_back({u, v, i});
        else p1.push_back({u, v, i});
    }
    solve(L, mid, p1);
    for (int i = R; i > mid; --i)
        for (auto id: p[i]) add(id, -1);
    solve(mid + 1, R, p2);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= n; ++i) p[h[i]].push_back(i);
    vector <dta> task;
    for (int i = 1; i <= q; ++i) {
        int L, R;
        cin >> L >> R;
        task.push_back({L, R, i});
    }
    solve(0, n, task);
    for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

Compilation message

index.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
index.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
index.cpp: In function 'void solve(int, int, std::vector<dta>&)':
index.cpp:36:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |         for (auto [u, v, i]: task) ans[i] = L;
      |                   ^
index.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid = L + R >> 1;
      |               ~~^~~
index.cpp:43:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for (auto [u, v, i]: task) {
      |               ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 4 ms 5152 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 4 ms 5156 KB Output is correct
6 Correct 3 ms 5172 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5196 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 4 ms 5152 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 4 ms 5156 KB Output is correct
6 Correct 3 ms 5172 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5196 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 69 ms 12164 KB Output is correct
12 Correct 57 ms 12312 KB Output is correct
13 Correct 56 ms 12100 KB Output is correct
14 Correct 55 ms 12276 KB Output is correct
15 Correct 61 ms 12264 KB Output is correct
16 Correct 61 ms 12188 KB Output is correct
17 Correct 55 ms 12288 KB Output is correct
18 Correct 56 ms 12276 KB Output is correct
19 Correct 74 ms 12244 KB Output is correct
20 Correct 63 ms 12184 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 4 ms 5152 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 4 ms 5156 KB Output is correct
6 Correct 3 ms 5172 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5196 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 69 ms 12164 KB Output is correct
12 Correct 57 ms 12312 KB Output is correct
13 Correct 56 ms 12100 KB Output is correct
14 Correct 55 ms 12276 KB Output is correct
15 Correct 61 ms 12264 KB Output is correct
16 Correct 61 ms 12188 KB Output is correct
17 Correct 55 ms 12288 KB Output is correct
18 Correct 56 ms 12276 KB Output is correct
19 Correct 74 ms 12244 KB Output is correct
20 Correct 63 ms 12184 KB Output is correct
21 Correct 260 ms 34524 KB Output is correct
22 Correct 270 ms 34404 KB Output is correct
23 Correct 312 ms 34744 KB Output is correct
24 Correct 254 ms 34744 KB Output is correct
25 Correct 291 ms 34548 KB Output is correct
26 Correct 292 ms 34868 KB Output is correct
27 Correct 329 ms 33908 KB Output is correct
28 Correct 312 ms 34616 KB Output is correct
29 Correct 283 ms 34584 KB Output is correct
30 Correct 257 ms 34576 KB Output is correct