#include <bits/stdc++.h>
using namespace std;
const int DIM = 1000005;
const int INF = 0x3f3f3f3f;
pair<int, int> sgt[DIM * 4];
void updateLazy(int nd, int le, int ri) {
if (sgt[nd].second) {
sgt[nd].first += sgt[nd].second;
if (le != ri) {
sgt[nd * 2].second += sgt[nd].second;
sgt[nd * 2 + 1].second += sgt[nd].second; }
sgt[nd].second = 0; } }
void update(int nd, int le, int ri, int st, int en, int vl) {
updateLazy(nd, le, ri);
if (ri < st or en < le or en < st) {
return; }
if (st <= le and ri <= en) {
sgt[nd].second += vl; updateLazy(nd, le, ri); }
else {
int md = (le + ri) / 2;
update(nd * 2, le, md, st, en, vl);
update(nd * 2 + 1, md + 1, ri, st, en, vl);
sgt[nd].first = max(sgt[nd * 2].first, sgt[nd * 2 + 1].first); } }
vector<int> countScans(vector<int> arr, vector<int> pos, vector<int> val) {
vector<pair<int, int>> crd; vector<int> sol(arr.size());
for (int i = 0; i < arr.size(); ++i) {
crd.push_back(make_pair(arr[i], i)); }
for (int i = 0; i < pos.size(); ++i) {
crd.push_back(make_pair(val[i], pos[i])); }
sort(crd.begin(), crd.end());
crd.resize(unique(crd.begin(), crd.end()) - crd.begin());
int n = arr.size(), q = pos.size(), s = crd.size();
update(1, 0, s - 1, 0, s - 1, -INF);
for (int i = 0; i < n; ++i) {
int ps = lower_bound(crd.begin(), crd.end(), make_pair(arr[i], i)) - crd.begin();
update(1, 0, s - 1, ps, ps, INF + i); update(1, 0, s - 1, ps + 1, s - 1, -1); }
for (int i = 0; i < q; ++i) {
int p = pos[i], v = val[i], ps;
ps = lower_bound(crd.begin(), crd.end(), make_pair(arr[p], p)) - crd.begin();
update(1, 0, s - 1, ps, ps, -INF - p); update(1, 0, s - 1, ps + 1, s - 1, +1); arr[p] = v;
ps = lower_bound(crd.begin(), crd.end(), make_pair(arr[p], p)) - crd.begin();
update(1, 0, s - 1, ps, ps, +INF + p); update(1, 0, s - 1, ps + 1, s - 1, -1); sol[i] = sgt[1].first; }
return sol; }
/*
#ifdef HOME
int main(void) {
freopen("bubblesort2.in", "r", stdin);
freopen("bubblesort2.out", "w", stdout);
int n, m; cin >> n >> m;
vector<int> arr(n), pos(m), val(m), sol;
for (int i = 0; i < n; ++i) {
cin >> arr[i]; }
for (int i = 0; i < m; ++i) {
cin >> pos[i] >> val[i]; }
sol = countScans(arr, pos, val);
for (int i = 0; i < m; ++i) {
cout << sol[i] << "\n"; }
return 0; }
#endif
*/
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < arr.size(); ++i) {
~~^~~~~~~~~~~~
bubblesort2.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < pos.size(); ++i) {
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
1780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
