Submission #788229

#TimeUsernameProblemLanguageResultExecution timeMemory
788229Charizard2021Bubble Sort 2 (JOI18_bubblesort2)C++17
100 / 100
1974 ms51528 KiB
#include<bits/stdc++.h> using namespace std; const int N = 1000001; vector<pair<int, int> > val; int T[N << 2], SegTree[N << 2]; void push(int s, int l, int r) { if (!SegTree[s]){ return; } T[s] += SegTree[s]; if (l != r) { SegTree[s << 1] += SegTree[s]; SegTree[s << 1 | 1] += SegTree[s]; } SegTree[s] = 0; } void up(int s, int l, int r, int from, int to, int val) { push(s, l, r); if (l > to || r < from) return; if (from <= l && r <= to) { SegTree[s] += val; push(s, l, r); return; } int mid = l + r >> 1; up(s << 1, l, mid, from, to, val); up(s << 1 | 1, mid + 1, r, from, to, val); T[s] = max(T[s << 1], T[s << 1 | 1]); } vector<int> countScans(vector<int> a, vector<int> pos, vector<int> val2) { vector<int> ans(pos.size()); int n = a.size(); for(int i = 0; i < n; i++){ val.push_back(make_pair(a[i], i)); } for(int i = 0; i < pos.size(); i++){ val.push_back(make_pair(val2[i], pos[i])); } sort(val.begin(), val.end()); val.resize(unique(val.begin(), val.end()) - val.begin()); int m = val.size(); for(int i = 0; i < n; i++) { int idx = upper_bound(val.begin(), val.end(), make_pair(a[i], i)) - val.begin(); up(1, 1, m, idx, idx, i + 1); up(1, 1, m, idx, m, -1); } for(int i = 0; i < pos.size(); i++) { int idx = upper_bound(val.begin(), val.end(), make_pair(a[pos[i]], pos[i])) - val.begin(); up(1, 1, m, idx, idx, -pos[i] - 1); up(1, 1, m, idx, m, 1); a[pos[i]] = val2[i]; idx = upper_bound(val.begin(), val.end(), make_pair(val2[i], pos[i])) - val.begin(); up(1, 1, m, idx, idx, pos[i] + 1); up(1, 1, m, idx, m, -1); ans[i] = T[1]; } return ans; }

Compilation message (stderr)

bubblesort2.cpp: In function 'void up(int, int, int, int, int, int)':
bubblesort2.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int mid = l + r >> 1;
      |               ~~^~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i = 0; i < pos.size(); i++){
      |                    ~~^~~~~~~~~~~~
bubblesort2.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i = 0; i < pos.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...