Submission #504080

#TimeUsernameProblemLanguageResultExecution timeMemory
504080hoanghq2004Index (COCI21_index)C++14
110 / 110
329 ms34868 KiB
#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 (stderr)

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) {
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...