#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
const int INF=0x3f3f3f3f;
const int N=1e6+5;
int n, q, off=1, ma=0;
vector <int> ppp, pospos, valval, saz;
set <int> S[N];
int T[2*N], prop[2*N];
void propag(int pos, int lo, int hi) {
if (prop[pos]==0) return;
T[pos]+=prop[pos];
if (pos<off) {
prop[pos*2]+=prop[pos];
prop[pos*2+1]+=prop[pos];
}
prop[pos]=0;
}
int query(int lo, int hi, int pos, int a, int b) {
propag(pos, lo, hi);
if (lo>=b || hi<=a) return 0;
if (lo>=a && hi<=b) return T[pos];
int mid=(lo+hi)/2;
return max(query(lo, mid, pos*2, a, b), query(mid, hi, pos*2+1, a, b));
}
void update(int lo, int hi, int pos, int a, int b, int val) {
propag(pos, lo, hi);
if (lo>=b || hi<=a) return;
if (lo>=a && hi<=b) {
prop[pos]+=val;
propag(pos, lo, hi);
return;
}
int mid=(lo+hi)/2;
update(lo, mid, pos*2, a, b, val);
update(mid, hi, pos*2+1, a, b, val);
T[pos]=max(T[pos*2], T[pos*2+1]);
}
void load() {
int nn, qq;
scanf("%d %d", &nn, &qq);
for (int i=0; i<nn; ++i) {
int x;
scanf("%d", &x);
ppp.pb(x);
}
for (int i=0; i<qq; ++i) {
int a, b;
scanf("%d %d", &a, &b);
pospos.pb(a);
valval.pb(b);
}
}
void countScans(vector <int> p, vector <int> Pos, vector <int> Val) {
n=p.size();
q=Pos.size();
for (int i=0; i<n; ++i) saz.pb(p[i]);
for (int i=0; i<q; ++i) saz.pb(Val[i]);
sort(saz.begin(), saz.end());
for (int i=0; i<n; ++i) {
p[i]=lower_bound(saz.begin(), saz.end(), p[i])-saz.begin()+1;
S[p[i]].insert(-i);
ma=max(ma, p[i]);
}
for (int i=0; i<q; ++i) {
Val[i]=lower_bound(saz.begin(), saz.end(), Val[i])-saz.begin()+1;
ma=max(ma, Val[i]);
}
while (off<ma) off*=2;
int zbr=0;
for (int i=1; i<=ma; ++i) {
zbr+=S[i].size();
S[i].insert(-1);
T[off+i]=-(*S[i].begin())-(zbr-1);
}
for (int i=off-1; i>0; --i) T[i]=max(T[i*2], T[i*2+1]);
for (int i=0; i<q; ++i) {
int x=p[Pos[i]], mi=-(*S[x].begin());
S[x].erase(-Pos[i]);
update(0, off, 1, x, x+1, mi+(*S[x].begin()));
int mii=-(*S[Val[i]].begin());
S[Val[i]].insert(-Pos[i]);
update(0, off, 1, Val[i], Val[i]+1, -(*S[Val[i]].begin())-mii);
if (x<Val[i]) {
update(0, off, 1, x+1, Val[i], -1);
}
else {
update(0, off, 1, Val[i]+1, x, 1);
}
printf("%d\n", query(0, off, 1, 1, ma));
}
}
//int main() {
// load();
// countScans(ppp, pospos, valval);
// return 0;
//}
Compilation message
bubblesort2.cpp: In function 'void load()':
bubblesort2.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &nn, &qq);
~~~~~^~~~~~~~~~~~~~~~~~~
bubblesort2.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
bubblesort2.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
98 ms |
94584 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 |
98 ms |
94584 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 |
105 ms |
98236 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 |
98 ms |
94584 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
