Submission #547759

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547759	2022-04-11T16:00:31 Z	cig32	Bubble Sort 2 (JOI18_bubblesort2)	C++17	Compilation error	0 ms	0 KB

bubblesort2

#include "bubblesort2.h"
 
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int __int128
#define long long __int128
typedef tree<pair<long long, long long>, null_type, less<pair<long long, long long> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int lmao = 4001000;
int qwq = 1000003;
struct node {
  long long upd = 0, val = 0;
} st[lmao];
 
void u(int l, int r, int constl, int constr, int idx, long long val) {
  if(l <= constl && constr <= r) {
    st[idx].upd += val;
    st[idx].val += val;
    return;
  }
  int mid = (constl + constr) >> 1;
  st[2*idx+1].upd += st[idx].upd;
  st[2*idx+2].upd += st[idx].upd;
  st[2*idx+1].val += st[idx].upd;
  st[2*idx+2].val += st[idx].upd;
  st[idx].upd = 0;
  if(mid < l || r < constl) u(l, r, mid+1, constr, 2*idx+2, val);
  else if(constr < l || r < mid+1) u(l, r, constl, mid, 2*idx+1, val);
  else {
    u(l, r, constl, mid, 2*idx + 1, val);
    u(l, r, mid+1, constr, 2*idx + 2, val);
  }
  st[idx].val = max(st[2*idx+1].val, st[2*idx+2].val);
}
 
long long qu(int l, int r, int constl, int constr, int idx) {
  if(l <= constl && constr <= r) return st[idx].val;
  int mid = (constl + constr) >> 1;
  st[2*idx+1].upd += st[idx].upd;
  st[2*idx+2].upd += st[idx].upd;
  st[2*idx+1].val += st[idx].upd;
  st[2*idx+2].val += st[idx].upd;
  st[idx].upd = 0;
  if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
  else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
  else {
    return max(qu(l, r, constl, mid, 2*idx+1), qu(l, r, mid+1, constr, 2*idx+2));
  }
}
 
void range_add(int l, int r, long long v) {
  u(l, r, 0, qwq, 0, v);
}
 
long long query_max(int l, int r) {
  return qu(l, r, 0, qwq, 0);
}
 
const long long onosan = -1e10;
std::vector<int32_t> countScans(std::vector<int32_t> A,std::vector<int32_t> X,std::vector<int32_t> V){
  ordered_set ost;
  int N=A.size();
	int Q=X.size();
	std::vector<int32_t> answer(Q);
  set<int> s;
  for(int i=0; i<N; i++) {
    s.insert(A[i]);
  }
  for(int i=0; i<Q; i++) s.insert(V[i]);
  map<int, int> is;
  int nxt = 0;
  for(int x: s) {
    is[x] = nxt++;
  }
  for(int i=0; i<N; i++) A[i] = is[A[i]];
  for(int i=0; i<Q; i++) V[i] = is[V[i]];
  for(int i=0; i<N; i++) ost.insert({A[i], i});
  pair<int, int> B[N];
  for(int i=0; i<N; i++) {
    B[i] = {A[i], i};
  }
  sort(B, B+N);
  multiset<pair<long long, long long> > ms[N+Q];
  map<long long, long long> ono[N+Q];
  for(int i=0; i<N; i++) {
    ms[B[i].first].insert({B[i].second - i, B[i].second});
    ono[B[i].first][B[i].second] = B[i].second - i;
  }
  for(int i=0; i<N+Q; i++) {
    if(ms[i].empty()) {
      range_add(i, i, onosan);
    }
    else {
      range_add(i, i, (*ms[i].rbegin()).first);
    }
  }
  for(int i=0; i<Q; i++) { 
    int x = A[X[i]];
    int y = V[i];
    if(A[X[i]] == V[i]) {
      answer[i] = query_max(0, N+Q - 1);
      continue;
    }
    if(x > y) swap(x, y);
    if(x + 1 < y) {
      if(A[X[i]] > V[i]) {
        range_add(x+1, y-1, -1);
      }
      else {
        range_add(x+1, y-1, 1);
      }
    }
    x = A[X[i]];
    y = V[i];
    int one = ms[x].size();
    ms[x].erase({ono[x][X[i]], X[i]});
    int two = ms[x].size();
    assert(one != two);
    if(ms[x].size()) {
      long long ogname = query_max(x, x);
      long long q = (*ms[x].rbegin()).second;
      ost.erase({x, X[i]});
      ost.insert({y, X[i]});
      range_add(x, x, q - (int)ost.order_of_key({A[q], q}) - ogname);
      //cout << "tar " << q - (int)ost.order_of_key({A[q], q}) << "\n";
      ost.erase({y, X[i]});
    }
    else {
    //  cout << "rip :rofl:\n";
      ost.erase({x, X[i]});
      long long ogname = query_max(x, x);
      range_add(x, x, onosan - ogname); // res = -1e17
    }
    ost.insert({y, X[i]});
    A[X[i]] = V[i];
    ms[y].insert({X[i] - (int)ost.order_of_key({V[i], X[i]}), X[i]});
    ono[y][X[i]] = X[i] - (int)ost.order_of_key({V[i], X[i]});
   // cout << X[i] << " " << (int)ost.order_of_key({V[i], X[i]}) << " " << X[i] - (int)ost.order_of_key({V[i], X[i]}) << " g\n";
    long long q = (*ms[y].rbegin()).second;
    long long ogname = query_max(V[i], V[i]);
    range_add(V[i], V[i], q - (int)ost.order_of_key({A[q], q}) - ogname);
    answer[i] = query_max(0, N + Q - 1);
    /*
    pair<int, int> B[N];
    for(int j=0; j<N; j++) B[j] = {A[j], j};
    sort(B, B+N);
    int expected = 0;
    for(int j=0; j<N; j++) expected = max(expected, B[j].second - j);
    if(expected != answer[i]) {
      cout << "fuck!!\n";
    //  cout << "query "<<i<<": expected "<<expected<<" found "<<answer[i]<<"\n";
    }
    // for(int j=0; j<N+Q; j++) cout << (query_max(j, j) < -1e15 ? "q" : to_string(query_max(j, j))) << " ";
    //  cout << "\n";
    */
  }
  
	return answer;
}

Compilation message

bubblesort2.cpp:16:19: error: two or more data types in declaration of 'type name'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:17:19: note: in expansion of macro 'long'
   17 | typedef tree<pair<long long, long long>, null_type, less<pair<long long, long long> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
      |                   ^~~~
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'type name'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:17:30: note: in expansion of macro 'long'
   17 | typedef tree<pair<long long, long long>, null_type, less<pair<long long, long long> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
      |                              ^~~~
bubblesort2.cpp:17:39: error: template argument 1 is invalid
   17 | typedef tree<pair<long long, long long>, null_type, less<pair<long long, long long> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
      |                                       ^
bubblesort2.cpp:17:39: error: template argument 2 is invalid
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'type name'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:17:63: note: in expansion of macro 'long'
   17 | typedef tree<pair<long long, long long>, null_type, less<pair<long long, long long> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
      |                                                               ^~~~
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'type name'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:17:74: note: in expansion of macro 'long'
   17 | typedef tree<pair<long long, long long>, null_type, less<pair<long long, long long> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
      |                                                                          ^~~~
bubblesort2.cpp:17:83: error: template argument 1 is invalid
   17 | typedef tree<pair<long long, long long>, null_type, less<pair<long long, long long> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
      |                                                                                   ^
bubblesort2.cpp:17:83: error: template argument 2 is invalid
bubblesort2.cpp:17:85: error: template argument 1 is invalid
   17 | typedef tree<pair<long long, long long>, null_type, less<pair<long long, long long> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
      |                                                                                     ^
bubblesort2.cpp:17:134: error: template argument 1 is invalid
   17 | typedef tree<pair<long long, long long>, null_type, less<pair<long long, long long> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
      |                                                                                                                                      ^
bubblesort2.cpp:17:134: error: template argument 3 is invalid
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'upd'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:22:3: note: in expansion of macro 'long'
   22 |   long long upd = 0, val = 0;
      |   ^~~~
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'val'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:22:3: note: in expansion of macro 'long'
   22 |   long long upd = 0, val = 0;
      |   ^~~~
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'val'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:25:55: note: in expansion of macro 'long'
   25 | void u(int l, int r, int constl, int constr, int idx, long long val) {
      |                                                       ^~~~
bubblesort2.cpp: In function 'void u(...)':
bubblesort2.cpp:26:6: error: 'l' was not declared in this scope
   26 |   if(l <= constl && constr <= r) {
      |      ^
bubblesort2.cpp:26:11: error: 'constl' was not declared in this scope; did you mean 'cosl'?
   26 |   if(l <= constl && constr <= r) {
      |           ^~~~~~
      |           cosl
bubblesort2.cpp:26:21: error: 'constr' was not declared in this scope
   26 |   if(l <= constl && constr <= r) {
      |                     ^~~~~~
bubblesort2.cpp:26:31: error: 'r' was not declared in this scope
   26 |   if(l <= constl && constr <= r) {
      |                               ^
bubblesort2.cpp:27:8: error: 'idx' was not declared in this scope; did you mean 'index'?
   27 |     st[idx].upd += val;
      |        ^~~
      |        index
bubblesort2.cpp:27:20: error: 'val' was not declared in this scope
   27 |     st[idx].upd += val;
      |                    ^~~
bubblesort2.cpp:31:14: error: 'constl' was not declared in this scope; did you mean 'cosl'?
   31 |   int mid = (constl + constr) >> 1;
      |              ^~~~~~
      |              cosl
bubblesort2.cpp:31:23: error: 'constr' was not declared in this scope
   31 |   int mid = (constl + constr) >> 1;
      |                       ^~~~~~
bubblesort2.cpp:32:8: error: 'idx' was not declared in this scope
   32 |   st[2*idx+1].upd += st[idx].upd;
      |        ^~~
bubblesort2.cpp:37:12: error: 'l' was not declared in this scope
   37 |   if(mid < l || r < constl) u(l, r, mid+1, constr, 2*idx+2, val);
      |            ^
bubblesort2.cpp:37:17: error: 'r' was not declared in this scope
   37 |   if(mid < l || r < constl) u(l, r, mid+1, constr, 2*idx+2, val);
      |                 ^
bubblesort2.cpp:37:61: error: 'val' was not declared in this scope
   37 |   if(mid < l || r < constl) u(l, r, mid+1, constr, 2*idx+2, val);
      |                                                             ^~~
bubblesort2.cpp:38:66: error: 'val' was not declared in this scope
   38 |   else if(constr < l || r < mid+1) u(l, r, constl, mid, 2*idx+1, val);
      |                                                                  ^~~
bubblesort2.cpp:40:37: error: 'val' was not declared in this scope
   40 |     u(l, r, constl, mid, 2*idx + 1, val);
      |                                     ^~~
bubblesort2.cpp: At global scope:
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'qu'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:46:1: note: in expansion of macro 'long'
   46 | long long qu(int l, int r, int constl, int constr, int idx) {
      | ^~~~
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'v'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:61:30: note: in expansion of macro 'long'
   61 | void range_add(int l, int r, long long v) {
      |                              ^~~~
bubblesort2.cpp: In function 'void range_add(...)':
bubblesort2.cpp:62:5: error: 'l' was not declared in this scope
   62 |   u(l, r, 0, qwq, 0, v);
      |     ^
bubblesort2.cpp:62:8: error: 'r' was not declared in this scope
   62 |   u(l, r, 0, qwq, 0, v);
      |        ^
bubblesort2.cpp:62:22: error: 'v' was not declared in this scope
   62 |   u(l, r, 0, qwq, 0, v);
      |                      ^
bubblesort2.cpp: At global scope:
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'query_max'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:65:1: note: in expansion of macro 'long'
   65 | long long query_max(int l, int r) {
      | ^~~~
bubblesort2.cpp:69:1: error: two or more data types in declaration of 'onosan'
   69 | const long long onosan = -1e10;
      | ^~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:87:30: error: request for member 'insert' in 'ost', which is of non-class type 'ordered_set' {aka 'int'}
   87 |   for(int i=0; i<N; i++) ost.insert({A[i], i});
      |                              ^~~~~~
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'type name'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:93:17: note: in expansion of macro 'long'
   93 |   multiset<pair<long long, long long> > ms[N+Q];
      |                 ^~~~
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'type name'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:93:28: note: in expansion of macro 'long'
   93 |   multiset<pair<long long, long long> > ms[N+Q];
      |                            ^~~~
bubblesort2.cpp:93:37: error: template argument 1 is invalid
   93 |   multiset<pair<long long, long long> > ms[N+Q];
      |                                     ^
bubblesort2.cpp:93:37: error: template argument 2 is invalid
bubblesort2.cpp:93:39: error: template argument 1 is invalid
   93 |   multiset<pair<long long, long long> > ms[N+Q];
      |                                       ^
bubblesort2.cpp:93:39: error: template argument 2 is invalid
bubblesort2.cpp:93:39: error: template argument 3 is invalid
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'type name'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:94:7: note: in expansion of macro 'long'
   94 |   map<long long, long long> ono[N+Q];
      |       ^~~~
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'type name'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:94:18: note: in expansion of macro 'long'
   94 |   map<long long, long long> ono[N+Q];
      |                  ^~~~
bubblesort2.cpp:94:27: error: template argument 1 is invalid
   94 |   map<long long, long long> ono[N+Q];
      |                           ^
bubblesort2.cpp:94:27: error: template argument 2 is invalid
bubblesort2.cpp:94:27: error: template argument 3 is invalid
bubblesort2.cpp:94:27: error: template argument 4 is invalid
bubblesort2.cpp:96:20: error: request for member 'insert' in 'ms[B[i].std::pair<__int128, __int128>::first]', which is of non-class type 'int'
   96 |     ms[B[i].first].insert({B[i].second - i, B[i].second});
      |                    ^~~~~~
bubblesort2.cpp:97:20: error: invalid types 'int[__int128]' for array subscript
   97 |     ono[B[i].first][B[i].second] = B[i].second - i;
      |                    ^
bubblesort2.cpp:100:14: error: request for member 'empty' in 'ms[i]', which is of non-class type 'int'
  100 |     if(ms[i].empty()) {
      |              ^~~~~
bubblesort2.cpp:101:23: error: 'onosan' was not declared in this scope
  101 |       range_add(i, i, onosan);
      |                       ^~~~~~
bubblesort2.cpp:104:31: error: request for member 'rbegin' in 'ms[i]', which is of non-class type 'int'
  104 |       range_add(i, i, (*ms[i].rbegin()).first);
      |                               ^~~~~~
bubblesort2.cpp:111:19: error: 'query_max' was not declared in this scope
  111 |       answer[i] = query_max(0, N+Q - 1);
      |                   ^~~~~~~~~
bubblesort2.cpp:125:21: error: request for member 'size' in 'ms[x]', which is of non-class type 'int'
  125 |     int one = ms[x].size();
      |                     ^~~~
bubblesort2.cpp:126:11: error: request for member 'erase' in 'ms[x]', which is of non-class type 'int'
  126 |     ms[x].erase({ono[x][X[i]], X[i]});
      |           ^~~~~
bubblesort2.cpp:126:24: error: invalid types 'int[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
  126 |     ms[x].erase({ono[x][X[i]], X[i]});
      |                        ^
bubblesort2.cpp:127:21: error: request for member 'size' in 'ms[x]', which is of non-class type 'int'
  127 |     int two = ms[x].size();
      |                     ^~~~
bubblesort2.cpp:129:14: error: request for member 'size' in 'ms[x]', which is of non-class type 'int'
  129 |     if(ms[x].size()) {
      |              ^~~~
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'ogname'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:130:7: note: in expansion of macro 'long'
  130 |       long long ogname = query_max(x, x);
      |       ^~~~
bubblesort2.cpp:130:26: error: 'query_max' was not declared in this scope
  130 |       long long ogname = query_max(x, x);
      |                          ^~~~~~~~~
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'q'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:131:7: note: in expansion of macro 'long'
  131 |       long long q = (*ms[x].rbegin()).second;
      |       ^~~~
bubblesort2.cpp:131:29: error: request for member 'rbegin' in 'ms[x]', which is of non-class type 'int'
  131 |       long long q = (*ms[x].rbegin()).second;
      |                             ^~~~~~
bubblesort2.cpp:132:11: error: request for member 'erase' in 'ost', which is of non-class type 'ordered_set' {aka 'int'}
  132 |       ost.erase({x, X[i]});
      |           ^~~~~
bubblesort2.cpp:133:11: error: request for member 'insert' in 'ost', which is of non-class type 'ordered_set' {aka 'int'}
  133 |       ost.insert({y, X[i]});
      |           ^~~~~~
bubblesort2.cpp:134:23: error: 'q' was not declared in this scope
  134 |       range_add(x, x, q - (int)ost.order_of_key({A[q], q}) - ogname);
      |                       ^
bubblesort2.cpp:134:36: error: request for member 'order_of_key' in 'ost', which is of non-class type 'ordered_set' {aka 'int'}
  134 |       range_add(x, x, q - (int)ost.order_of_key({A[q], q}) - ogname);
      |                                    ^~~~~~~~~~~~
bubblesort2.cpp:134:62: error: 'ogname' was not declared in this scope; did you mean 'tzname'?
  134 |       range_add(x, x, q - (int)ost.order_of_key({A[q], q}) - ogname);
      |                                                              ^~~~~~
      |                                                              tzname
bubblesort2.cpp:136:11: error: request for member 'erase' in 'ost', which is of non-class type 'ordered_set' {aka 'int'}
  136 |       ost.erase({y, X[i]});
      |           ^~~~~
bubblesort2.cpp:140:11: error: request for member 'erase' in 'ost', which is of non-class type 'ordered_set' {aka 'int'}
  140 |       ost.erase({x, X[i]});
      |           ^~~~~
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'ogname'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:141:7: note: in expansion of macro 'long'
  141 |       long long ogname = query_max(x, x);
      |       ^~~~
bubblesort2.cpp:141:26: error: 'query_max' was not declared in this scope
  141 |       long long ogname = query_max(x, x);
      |                          ^~~~~~~~~
bubblesort2.cpp:142:23: error: 'onosan' was not declared in this scope
  142 |       range_add(x, x, onosan - ogname); // res = -1e17
      |                       ^~~~~~
bubblesort2.cpp:142:32: error: 'ogname' was not declared in this scope; did you mean 'tzname'?
  142 |       range_add(x, x, onosan - ogname); // res = -1e17
      |                                ^~~~~~
      |                                tzname
bubblesort2.cpp:144:9: error: request for member 'insert' in 'ost', which is of non-class type 'ordered_set' {aka 'int'}
  144 |     ost.insert({y, X[i]});
      |         ^~~~~~
bubblesort2.cpp:146:11: error: request for member 'insert' in 'ms[y]', which is of non-class type 'int'
  146 |     ms[y].insert({X[i] - (int)ost.order_of_key({V[i], X[i]}), X[i]});
      |           ^~~~~~
bubblesort2.cpp:146:35: error: request for member 'order_of_key' in 'ost', which is of non-class type 'ordered_set' {aka 'int'}
  146 |     ms[y].insert({X[i] - (int)ost.order_of_key({V[i], X[i]}), X[i]});
      |                                   ^~~~~~~~~~~~
bubblesort2.cpp:147:11: error: invalid types 'int[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
  147 |     ono[y][X[i]] = X[i] - (int)ost.order_of_key({V[i], X[i]});
      |           ^
bubblesort2.cpp:147:36: error: request for member 'order_of_key' in 'ost', which is of non-class type 'ordered_set' {aka 'int'}
  147 |     ono[y][X[i]] = X[i] - (int)ost.order_of_key({V[i], X[i]});
      |                                    ^~~~~~~~~~~~
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'q'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:149:5: note: in expansion of macro 'long'
  149 |     long long q = (*ms[y].rbegin()).second;
      |     ^~~~
bubblesort2.cpp:149:27: error: request for member 'rbegin' in 'ms[y]', which is of non-class type 'int'
  149 |     long long q = (*ms[y].rbegin()).second;
      |                           ^~~~~~
bubblesort2.cpp:16:19: error: two or more data types in declaration of 'ogname'
   16 | #define long long __int128
      |                   ^~~~~~~~
bubblesort2.cpp:150:5: note: in expansion of macro 'long'
  150 |     long long ogname = query_max(V[i], V[i]);
      |     ^~~~
bubblesort2.cpp:150:24: e