Submission #522870

#TimeUsernameProblemLanguageResultExecution timeMemory
522870CraniXortBubble Sort 2 (JOI18_bubblesort2)C++17
0 / 100
18 ms3248 KiB
#include <bits/stdc++.h> std::ifstream fin("bubble.in"); std::ofstream fout("bubble.out"); struct Element { int value, pos, index, norm; static bool sortByValue(Element &a, Element &b) { if(a.value == b.value) return a.pos < b.pos; return a.value < b.value; } static bool sortByIndex(Element &a, Element &b) { return a.index < b.index; } void print() { fout << value << ' ' << pos << ' ' << index << ' ' << norm << '\n'; } }; class SegmTree { int size; std::vector <int> lazy, min; void propagate(int node) { lazy[2*node+1] += lazy[node]; lazy[2*node+2] += lazy[node]; min[2*node+1] += lazy[node]; min[2*node+2] += lazy[node]; lazy[node] = 0; } void set(int node, int left, int right, int pos, int value) { if(left == right) { min[node] = value; return; } propagate(node); int mid = (left + right) / 2; if(mid >= pos) set(2*node+1, left, mid, pos, value); else set(2*node+2, mid+1, right, pos, value); min[node] = std::min(min[2*node+1], min[2*node+2]); } void update(int node, int left, int right, int from, int to, int value) { if(left > to or right < from) return; propagate(node); if(from <= left and right <= to) { min[node] += value; lazy[node] += value; return; } int mid = (left + right) / 2; update(2*node+1, left, mid, from, to, value); update(2*node+2, mid+1, right, from, to, value); min[node] = std::min(min[2*node+1], min[2*node+2]); } int query(int node, int left, int right, int from, int to) { if(left > to or right < from) return 1e9; if(from <= left and right <= to) return min[node]; propagate(node); int mid = (left + right) / 2; int ans = std::min(query(2*node+1, left, mid, from, to), query(2*node+2, mid+1, right, from, to)); min[node] = std::min(min[2*node+1], min[2*node+2]); return ans; } public: SegmTree(int n) { size = 1; while(size < n) size *= 2; lazy.resize(2 * size); min.resize(2 * size); std::fill(min.begin(), min.end(), 1e9); } int getMin() { return min[0]; } int querySegm(int left, int right) { return query(0, 0, size-1, left, right); } void updateSegm(int left, int right, int value) { update(0, 0, size-1, left, right, value); } void setSegm(int pos, int value) { set(0, 0, size-1, pos, value); } }; class Bit { int size; std::vector <int> bit; public: Bit(int n) { size = n + 1; bit.resize(size + 1); } void update(int pos, int value) { pos ++; while(pos <= size) { bit[pos] += value; pos = pos + (pos & -pos); } } int query(int pos) { pos ++; int ans = 0; while(pos > 0) { ans += bit[pos]; pos = pos - (pos & -pos); } return ans; } }; std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){ std::vector <int> ans(X.size()); std::vector <Element> v; int n = A.size(); for(int i = 0, value; i < n; i ++) { value = A[i]; v.push_back({value, i, i, 0}); } int Q = X.size(); for(int i = 0, value, pos; i < Q; i ++) { pos = X[i]; value = V[i]; v.push_back({value, pos, n + i, 0}); } std::sort(v.begin(), v.end(), Element::sortByValue); for(int i = 1; i < v.size(); i ++) { int crt = v[i-1].norm; if(!(v[i].value == v[i-1].value and v[i].pos == v[i-1].pos)) crt ++; v[i].norm = crt; } std::sort(v.begin(), v.end(), Element::sortByIndex); SegmTree segm(n+Q); Bit bit(n+Q); for(int i = 0; i < n; i ++) { segm.setSegm(v[i].norm, v[i].pos - i); bit.update(v[i].norm, 1); } for(int i = n; i < n+Q; i ++) { int currPos = v[v[i].pos].norm; int nextPos = v[i].norm; v[v[i].pos].norm = v[i].norm; segm.setSegm(nextPos, bit.query(nextPos) - v[i].pos); segm.updateSegm(nextPos + 1, n+Q-1, 1); segm.updateSegm(currPos + 1, n+Q-1, -1); segm.setSegm(currPos, 1e9); // fout << -segm.getMin() << '\n'; ans[i-n] = -segm.getMin(); } return ans; } // int main() { // int n, Q; // fin >> n; // std::vector <int> v(n); // for(int i = 0; i < n; i ++) // fin >> v[i]; // fin >> Q; // std::vector <int> x(Q), val(Q); // for(int i = 0; i < Q; i ++) // fin >> x[i] >> val[i]; // std::vector <int> ans = countScans(v, x, val); // for(auto i: ans) // fout << i << '\n'; // return 0; // }

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:169:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Element>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |     for(int i = 1; i < v.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...