Submission #539256

#TimeUsernameProblemLanguageResultExecution timeMemory
539256LucaDantasBubble Sort 2 (JOI18_bubblesort2)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include "bubblesort2.h" using namespace std; constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar // constexpr int maxn = 1<<20, B = 700, inf = 0x3f3f3f3f; // subtasks brutao, mudar #include <bits/stdc++.h> #include "bubblesort2.h" using namespace std; constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar struct SegmentTree { int a[maxn]; void build(int node, int i, int j) { } void upd(int node, int i, int j, int l, int r, int v) { for(int i = l; i <= r; i++) a[i] += v; } int query() { int ans = 0; for(int i = 0; i < 8010; i++) ans = max(ans, a[i]); return ans; } } seg; void compress(vector<int>& A, vector<int>& V) { map<int,int> mp; for(int x : A) mp[x] = 0; for(int x : V) mp[x] = 0; int coord = 0; for(auto& it : mp) it.second = ++coord; for(int& x : A) x = mp[x]; for(int& x : V) x = mp[x]; } struct BIT { int bit[maxn]; void upd(int x, int v) { for(; x > 0; x -= x&-x) bit[x] += v; } int query(int x) { int ans = 0; for(; x < maxn; x += x&-x) ans += bit[x]; return ans; } void clear() { memset(bit, 0, sizeof bit); } } bit; vector<int> pareto; int ans[maxn]; bool foi[maxn]; vector<pair<int,int>> qr[maxn]; int FORA[maxn], DENTRO[maxn]; void rebuild(const vector<int>& A) { pareto.clear(); int N = (int)(A.size()); for(int i = 0; i < N; i++) { if(foi[i]) continue; while(pareto.size() && A[i] <= A[pareto.back()]) pareto.pop_back(); pareto.push_back(i); } bit.clear(); for(int i = 0; i < (int)A.size(); i++) { while(qr[i].size()) { auto [val, id] = qr[i].back(); qr[i].pop_back(); ans[id] = bit.query(val+1); } DENTRO[i] = bit.query(A[i]+1); if(!foi[i]) seg.a[i] = DENTRO[i]; else seg.a[i] = -inf; if(!foi[i]) bit.upd(A[i], 1); } seg.build(1, 0, N-1); } int bs(int x, const vector<int>& A) { int l = 0, r = (int)(pareto.size())-1, ans = -1; while(l <= r) { int m = (l+r) >> 1; if(A[pareto[m]] < x) ans = pareto[m], l = m+1; else r = m-1; } return ans; } std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){ int Q = (int)X.size(), N = (int)A.size(); compress(A, V); std::vector<int> answer(Q); for(int q = 0; q < Q; q += B) { vector<int> special; for(int add = 0; add < B && add+q < Q; add++) { qr[X[q+add]].push_back({V[q+add], q+add}); if(foi[X[q+add]]) continue; foi[X[q+add]] = 1; special.push_back(X[q+add]); } /* for(int i = 0; i < N; i++) if(!foi[i]) foi[i] = 1, special.push_back(i); */ rebuild(A); for(int add = 0; add < B && add+q < Q; add++) { int pos = X[q+add], val = V[q+add]; /* int last = bs(A[pos], A); if(last > pos) seg.upd(1, 0, N-1, pos, last, -1); */ A[pos] = val; { int last = bs(A[pos], A); if(last > pos) seg.upd(1, 0, N-1, pos, last, 1); } int especiais = 0; for(int x : special) { int aq = 0; for(int j = 0; j < x; j++) aq += A[j] > A[x]; especiais = max(especiais, aq); } answer[q+add] = max(seg.query(), especiais); } for(int x : special) foi[x] = 0; } return answer; } struct SegmentTree { int tree[maxn], lazy[maxn], a[maxn]; void flush(int node, int i, int j) { /* if(!lazy[node]) return; if(i != j) { lazy[node<<1] += lazy[node]; lazy[node<<1|1] += lazy[node]; } tree[node] += lazy[node]; lazy[node] = 0; */ } void build(int node, int i, int j) { /* lazy[node] = 0; if(i == j) return (void)(tree[node] = a[i]); int m = (i+j) >> 1; build(node<<1, i, m); build(node<<1|1, m+1, j); tree[node] = max(tree[node<<1], tree[node<<1|1]); */ } void upd(int node, int i, int j, int l, int r, int v) { /* flush(node, i, j); if(i > r || j < l) return; if(i >= l && j <= r) { lazy[node] += v; flush(node, i, j); return; } int m = (i+j) >> 1; upd(node<<1, i, m, l, r, v); upd(node<<1|1, m+1, j, l, r, v); tree[node] = max(tree[node<<1], tree[node<<1|1]); */ for(int i = l; i <= r; i++) a[i] += v; } int query() { int ans = 0; for(int i = 0; i < 8010; i++) ans = max(ans, a[i]); return ans; } // int query() { return tree[1] + lazy[1]; } // quero o maximo geral mesmo } seg; void compress(vector<int>& A, vector<int>& V) { map<int,int> mp; for(int x : A) mp[x] = 0; for(int x : V) mp[x] = 0; int coord = 0; for(auto& it : mp) it.second = ++coord; for(int& x : A) x = mp[x]; for(int& x : V) x = mp[x]; } struct BIT { int bit[maxn]; void upd(int x, int v) { for(; x > 0; x -= x&-x) bit[x] += v; } int query(int x) { int ans = 0; for(; x < maxn; x += x&-x) ans += bit[x]; return ans; } void clear() { memset(bit, 0, sizeof bit); } } bit; vector<int> pareto; int ans[maxn]; bool foi[maxn]; vector<pair<int,int>> qr[maxn]; int FORA[maxn], DENTRO[maxn]; void rebuild(const vector<int>& A) { pareto.clear(); int N = (int)(A.size()); for(int i = 0; i < N; i++) { if(foi[i]) continue; while(pareto.size() && A[i] <= A[pareto.back()]) pareto.pop_back(); pareto.push_back(i); } bit.clear(); for(int i = 0; i < (int)A.size(); i++) { while(qr[i].size()) { auto [val, id] = qr[i].back(); qr[i].pop_back(); ans[id] = bit.query(val+1); } DENTRO[i] = bit.query(A[i]+1); seg.a[i] = DENTRO[i], bit.upd(A[i], 1); } seg.build(1, 0, N-1); } int bs(int x, const vector<int>& A) { int l = 0, r = (int)(pareto.size())-1, ans = -1; while(l <= r) { int m = (l+r) >> 1; if(A[pareto[m]] < x) ans = pareto[m], l = m+1; else r = m-1; } return ans; } std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){ int Q = (int)X.size(), N = (int)A.size(); compress(A, V); std::vector<int> answer(Q); for(int q = 0; q < Q; q += B) { vector<int> special; for(int add = 0; add < B && add+q < Q; add++) { qr[X[q+add]].push_back({V[q+add], q+add}); if(foi[X[q+add]]) continue; foi[X[q+add]] = 1; special.push_back(X[q+add]); } /* for(int i = 0; i < N; i++) if(!foi[i]) foi[i] = 1, special.push_back(i); */ rebuild(A); // memset(FORA, 0, sizeof FORA); // memset(ans, 0, sizeof ans); /* for(int x : special) FORA[x] = 0; for(int x : special) for(int y : special) if(x < y && A[x] > A[y]) ++FORA[y]; */ for(int add = 0; add < B && add+q < Q; add++) { int pos = X[q+add], val = V[q+add]; int last = bs(A[pos], A); if(last > pos) seg.upd(1, 0, N-1, pos, last, -1); /* for(int x : special) { if(pos < x && A[pos] > A[x]) --FORA[x]; if(x < pos && A[x] > A[pos]) --FORA[pos]; } */ // DENTRO[pos] = ans[q+add]; A[pos] = val; last = bs(A[pos], A); if(last > pos) seg.upd(1, 0, N-1, pos, last, 1); // db /* DENTRO[pos] = 0; for(int j = 0; j < pos; j++) if(!foi[j] && A[j] > val) DENTRO[pos]++; */ /* for(int x : special) { if(pos < x && A[pos] > A[x]) ++FORA[x]; if(x < pos && A[x] > A[pos]) ++FORA[pos]; } */ int especiais = 0; for(int x : special) { // especiais = max(especiais, FORA[x] + DENTRO[x]); int aq = 0; for(int j = 0; j < x; j++) aq += A[j] > A[x]; especiais = max(especiais, aq); } answer[q+add] = max(seg.query(), especiais); } for(int x : special) foi[x] = 0; } return answer; }

Compilation message (stderr)

bubblesort2.cpp:11:15: error: redefinition of 'constexpr const int maxn'
   11 | constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
      |               ^~~~
bubblesort2.cpp:5:15: note: 'constexpr const int maxn' previously defined here
    5 | constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
      |               ^~~~
bubblesort2.cpp:11:29: error: redefinition of 'constexpr const int B'
   11 | constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
      |                             ^
bubblesort2.cpp:5:29: note: 'constexpr const int B' previously defined here
    5 | constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
      |                             ^
bubblesort2.cpp:11:36: error: redefinition of 'constexpr const int inf'
   11 | constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
      |                                    ^~~
bubblesort2.cpp:5:36: note: 'constexpr const int inf' previously defined here
    5 | constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
      |                                    ^~~
bubblesort2.cpp:161:8: error: redefinition of 'struct SegmentTree'
  161 | struct SegmentTree {
      |        ^~~~~~~~~~~
bubblesort2.cpp:13:8: note: previous definition of 'struct SegmentTree'
   13 | struct SegmentTree {
      |        ^~~~~~~~~~~
bubblesort2.cpp:202:3: error: conflicting declaration 'int seg'
  202 | } seg;
      |   ^~~
bubblesort2.cpp:27:3: note: previous declaration as 'SegmentTree seg'
   27 | } seg;
      |   ^~~
bubblesort2.cpp:204:6: error: redefinition of 'void compress(std::vector<int>&, std::vector<int>&)'
  204 | void compress(vector<int>& A, vector<int>& V) {
      |      ^~~~~~~~
bubblesort2.cpp:29:6: note: 'void compress(std::vector<int>&, std::vector<int>&)' previously defined here
   29 | void compress(vector<int>& A, vector<int>& V) {
      |      ^~~~~~~~
bubblesort2.cpp:221:8: error: redefinition of 'struct BIT'
  221 | struct BIT {
      |        ^~~
bubblesort2.cpp:46:8: note: previous definition of 'struct BIT'
   46 | struct BIT {
      |        ^~~
bubblesort2.cpp:234:3: error: conflicting declaration 'int bit'
  234 | } bit;
      |   ^~~
bubblesort2.cpp:59:3: note: previous declaration as 'BIT bit'
   59 | } bit;
      |   ^~~
bubblesort2.cpp:236:13: error: redefinition of 'std::vector<int> pareto'
  236 | vector<int> pareto;
      |             ^~~~~~
bubblesort2.cpp:61:13: note: 'std::vector<int> pareto' previously declared here
   61 | vector<int> pareto;
      |             ^~~~~~
bubblesort2.cpp:238:5: error: redefinition of 'int ans [1048576]'
  238 | int ans[maxn]; bool foi[maxn];
      |     ^~~
bubblesort2.cpp:63:5: note: 'int ans [1048576]' previously declared here
   63 | int ans[maxn]; bool foi[maxn];
      |     ^~~
bubblesort2.cpp:238:21: error: redefinition of 'bool foi [1048576]'
  238 | int ans[maxn]; bool foi[maxn];
      |                     ^~~
bubblesort2.cpp:63:21: note: 'bool foi [1048576]' previously declared here
   63 | int ans[maxn]; bool foi[maxn];
      |                     ^~~
bubblesort2.cpp:239:23: error: redefinition of 'std::vector<std::pair<int, int> > qr [1048576]'
  239 | vector<pair<int,int>> qr[maxn];
      |                       ^~
bubblesort2.cpp:64:23: note: 'std::vector<std::pair<int, int> > qr [1048576]' previously declared here
   64 | vector<pair<int,int>> qr[maxn];
      |                       ^~
bubblesort2.cpp:240:5: error: redefinition of 'int FORA [1048576]'
  240 | int FORA[maxn], DENTRO[maxn];
      |     ^~~~
bubblesort2.cpp:65:5: note: 'int FORA [1048576]' previously declared here
   65 | int FORA[maxn], DENTRO[maxn];
      |     ^~~~
bubblesort2.cpp:240:17: error: redefinition of 'int DENTRO [1048576]'
  240 | int FORA[maxn], DENTRO[maxn];
      |                 ^~~~~~
bubblesort2.cpp:65:17: note: 'int DENTRO [1048576]' previously declared here
   65 | int FORA[maxn], DENTRO[maxn];
      |                 ^~~~~~
bubblesort2.cpp:242:6: error: redefinition of 'void rebuild(const std::vector<int>&)'
  242 | void rebuild(const vector<int>& A) {
      |      ^~~~~~~
bubblesort2.cpp:67:6: note: 'void rebuild(const std::vector<int>&)' previously defined here
   67 | void rebuild(const vector<int>& A) {
      |      ^~~~~~~
bubblesort2.cpp:266:5: error: redefinition of 'int bs(int, const std::vector<int>&)'
  266 | int bs(int x, const vector<int>& A) {
      |     ^~
bubblesort2.cpp:96:5: note: 'int bs(int, const std::vector<int>&)' previously defined here
   96 | int bs(int x, const vector<int>& A) {
      |     ^~
bubblesort2.cpp:278:18: error: redefinition of 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)'
  278 | std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
      |                  ^~~~~~~~~~
bubblesort2.cpp:108:18: note: 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)' previously defined here
  108 | std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
      |                  ^~~~~~~~~~