Submission #673485

#TimeUsernameProblemLanguageResultExecution timeMemory
673485406Bubble Sort 2 (JOI18_bubblesort2)C++17
100 / 100
1820 ms41940 KiB
#include "bubblesort2.h" #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 50; const int INF = 1 << 25; int mx[4 * N], delta[4 * N]; vector<pair<int, int>> D; void add(int v, int l, int r, int L, int R, int d) { if (R <= L || R <= l || r <= L) return; if (l >= L && r <= R) { mx[v] += d; delta[v] += d; return; } int m = l + r >> 1; add(v<<1, l, m, L, R, d); add(v<<1|1, m, r, L, R, d); mx[v] = max(mx[v<<1], mx[v<<1|1]) + delta[v]; } vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){ int Q = X.size(); int n = A.size(); D.reserve(Q + n); for (int i = 0; i < n; i++) D.emplace_back(A[i], i); for (int i = 0; i < Q; i++) D.emplace_back(V[i], X[i]); sort(D.begin(), D.end()); D.resize(unique(D.begin(), D.end()) - D.begin()); for (int i = 0; i < A.size(); i++) { int ind = lower_bound(D.begin(), D.end(), make_pair(A[i], i)) - D.begin(); add(1, 0, D.size(), ind, ind + 1, +i); add(1, 0, D.size(), ind + 1, D.size(), -1); } vector<int> answer(Q); for (int i = 0; i < Q; i++) { int ind = lower_bound(D.begin(), D.end(), make_pair(A[X[i]], X[i])) - D.begin(); add(1, 0, D.size(), ind, ind + 1, -X[i]); add(1, 0, D.size(), ind + 1, D.size(), +1); ind = lower_bound(D.begin(), D.end(), make_pair(V[i], X[i])) - D.begin(); add(1, 0, D.size(), ind, ind + 1, +X[i]); add(1, 0, D.size(), ind + 1, D.size(), -1); A[X[i]] = V[i]; answer[i] = max(mx[1], 0); } return answer; }

Compilation message (stderr)

bubblesort2.cpp: In function 'void add(int, int, int, int, int, int)':
bubblesort2.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |  int m = l + r >> 1;
      |          ~~^~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i = 0; i < A.size(); i++) {
      |                  ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...