#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int const NMAX = 5e5;
int arr[1 + NMAX];
int const MMAX = 1e6;
int aib[1 + MMAX];
void update(int pos, int add, int m) {
//cerr << "Update : ";
for(int i = pos;i <= m;i = 2 * i - (i & (i-1))) {
//cerr << i << ' ';
aib[i] += add;
}
//cerr << ";\n";
}
long long query(int pos, int m) {
long long ans = 0;
//cerr << "Query : ";
for(int i = pos;i > 0;i = (i & (i-1))) {
ans += aib[i];
//cerr << i << ' ';
}
//cerr << ";\n";
return ans;
}
long long solve(int n, int m) {
for(int i = 1;i <= m;i++) {
aib[i] = 0;
}
long long ans = 0;
//cerr << " ";
for(int i = 0;i < n;i++) {
//cerr << arr[i] << ' ';
ans = max(ans, (query(m, m) - query(arr[i], m)));
update(arr[i], 1, m);
}
//cerr << "\n";
return ans;
}
vector <long long> countScans(vector <int> vec, vector <int> pos, vector <int> val) {
// Normalize
//cerr << "Normalize ... must be bad\n";
vector <int> all;
for(int i = 0;i < vec.size();i++){
all.push_back(vec[i]);
}
for(int i = 0;i < val.size();i++){
all.push_back(val[i]);
}
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
map <int, int> norm;
for(int i = 0;i < all.size();i++) {
norm[all[i]] = i+1;
}
int n = vec.size();
for(int i = 0;i < vec.size();i++) {
vec[i] = norm[vec[i]];
arr[i] = vec[i];
}
for(int i = 0;i < val.size();i++) {
val[i] = norm[val[i]];
}
//cerr << "Normalize Accepted : Failed Solve\n";
// Solve
vector <long long> ans;
int t = pos.size();
for(int q = 0;q < t;q++) {
arr[pos[q]] = val[q];
//cerr << " Can't solve this\n";
ans.push_back(solve(n, all.size()));
}
return ans;
}
/*
void test() {
int n, t;
cin >> n >> t;
vector <int> vec, pos, val;
vector <long long> ans;
for(int i = 0;i < n;i++) {
int c;
cin >> c;
vec.push_back(c);
}
for(int i = 0;i < t;i++) {
int c1, c2;
cin >> c1 >> c2;
pos.push_back(c1);
val.push_back(c2);
}
ans = countScans(vec, pos, val);
for(int i = 0;i < ans.size();i++) {
cout << ans[i] << ' ';
}
}
/*
Example:
4 2
1 2 3 4
0 3
2 1
4 4
1 2 3 4
0 5
1 5
2 5
3 5
int main() {
test();
return 0;
}
*/
Compilation message
bubblesort2.cpp:109:1: warning: "/*" within comment [-Wcomment]
109 | /*
|
bubblesort2.cpp: In function 'std::vector<long long int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i = 0;i < vec.size();i++){
| ~~^~~~~~~~~~~~
bubblesort2.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i = 0;i < val.size();i++){
| ~~^~~~~~~~~~~~
bubblesort2.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i = 0;i < all.size();i++) {
| ~~^~~~~~~~~~~~
bubblesort2.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 0;i < vec.size();i++) {
| ~~^~~~~~~~~~~~
bubblesort2.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i = 0;i < val.size();i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1020 ms |
2908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
