QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#657289 | #7787. Maximum Rating | JEdward | ML | 2ms | 13920kb | C++23 | 5.1kb | 2024-10-19 14:31:26 | 2024-10-19 14:31:27 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define ls(s) (s << 1)
#define rs(s) (s << 1 | 1)
#define endl '\n'
using namespace std;
const int N = 2e5 + 5;
const int inf = 1e9 + 10;
int n, q;
int a[N], aid[N];
int last[N];
pair<int, int> qry[N];
int qryid[N];
vector<int> b, MAP;
int tr[N << 2];
inline void build(int p, int pl, int pr){
if(pl == pr){
return tr[p] = b[pl], void();
}
int mid = pl + pr >> 1;
build(ls(p), pl, mid);
build(rs(p), mid + 1, pr);
tr[p] = tr[ls(p)] + tr[rs(p)];
}
inline void update(int p, int pl, int pr, int idx, int x){
if(pl == pr){
return tr[p] = x, void();
}
int mid = pl + pr >> 1;
if(idx <= mid) update(ls(p), pl, mid, idx, x);
else update(rs(p), mid+1, pr, idx, x);
tr[p] = tr[ls(p)] + tr[rs(p)];
}
inline int query(int p, int pl, int pr, int l, int r){
if(l <= pl && pr <= r){
return tr[p];
}
int mid = pl + pr >> 1, res = 0;
if(l <= mid) res += query(ls(p), pl, mid, l, r);
if(r > mid) res += query(rs(p), mid+1, pr, l, r);
return res;
}
inline int findfirst(int p, int pl, int pr, int l, int r, int x){
if(pl == pr){
if(tr[p] > x) return pl;
else return MAP.size();
}
int mid = pl + pr >> 1;
if(tr[ls(p)] > x){
return findfirst(ls(p), pl, mid, l, r, x);
}else {
return findfirst(rs(p), mid+1, pr, l, r, x);
}
return MAP.size();
}
inline int getid(int x){
return lower_bound(MAP.begin(), MAP.end(), x) - MAP.begin();
}
map<int, int> mp;
#define lowbit(x) (x & -x)
int T[N << 1];
inline void add(int x, int d){
for(int i=x;i<=MAP.size()+1;i+=lowbit(i)){
T[i] += d;
}
}
inline int gsum(int x){
int res = 0;
for(int i=x;i;i-=lowbit(i)){
res += T[i];
}
return res;
}
signed main(){
cin.tie(0)->ios::sync_with_stdio(0);
cin >> n >> q;
MAP.push_back(-1);
for(int i=1;i<=n;i++){
cin >> a[i];
if(a[i] > 0)
MAP.push_back(a[i]);
}
for(int i=1;i<=q;i++){
cin >> qry[i].first >> qry[i].second;
if(qry[i].second > 0){
MAP.push_back(qry[i].second);
}
}
sort(MAP.begin(), MAP.end());
for(int i=1;i<=n;i++){
if(a[i] > 0){
if(!mp.count(a[i])){
aid[i] = getid(a[i]);
mp[a[i]] = aid[i] + 1;
}else{
aid[i] = mp[a[i]];
mp[a[i]]++;
}
}
}
for(int i=1;i<=q;i++){
if(qry[i].second > 0){
if(!mp.count(qry[i].second)){
qryid[i] = getid(qry[i].second);
mp[qry[i].second] = qryid[i] + 1;
}else{
qryid[i] = mp[qry[i].second];
mp[qry[i].second]++;
}
}
}
b.resize(MAP.size() + 5);
int neg_sum = 0, neg_num = 0;
for(int i=1;i<=n;i++){
if(a[i] > 0){
b[aid[i]] = a[i];
last[i] = aid[i];
add(aid[i], 1);
}else{
neg_sum += -a[i];
neg_num++;
}
}
int len = (int)MAP.size() - 1;
build(1,1,len);
for(int i=1;i<=q;i++){
int L, R;
if(a[qry[i].first] <= 0 && qry[i].second <= 0){
// neg -> neg
neg_sum -= -a[qry[i].first];
a[qry[i].first] = qry[i].second;
neg_sum += -a[qry[i].first];
}else if(a[qry[i].first] <= 0 && qry[i].second > 0){
// neg -> pos
neg_sum -= -a[qry[i].first];
neg_num --;
a[qry[i].first] = qry[i].second;
last[qry[i].first] = qryid[i];
update(1,1,len,qryid[i],a[qry[i].first]);
add(qryid[i], 1);
}else if(a[qry[i].first] > 0 && qry[i].second <= 0){
// pos -> neg
neg_num ++;
a[qry[i].first] = qry[i].second;
neg_sum += -a[qry[i].first];
add(last[qry[i].first], -1);
update(1,1,len,last[qry[i].first],0);
}else if(a[qry[i].first] > 0 && qry[i].second > 0){
// pos -> pos
a[qry[i].first] = qry[i].second;
add(last[qry[i].first], -1);
update(1,1,len,last[qry[i].first],0);
last[qry[i].first] = qryid[i];
add(qryid[i], 1);
update(1,1,len,qryid[i],a[qry[i].first]);
}
R = n - neg_num;
L = findfirst(1,1,len,1,len,neg_sum);
// if(neg_sum == 0){
// L = 0;
// }
// cout << " findfirst " << L << endl;
int pos_num = n - neg_num;
L = pos_num - gsum(L - 1);
// for(int j=1;j<=n;j++){
// cout << a[j] << " \n"[j == n];
// }
// for(int j=1;j<=len;j++){
// cout << query(1,1,len,j,j) << " \n"[j == len];
// }
// for(int j=1;j<=n;j++){
// cout << last[j] << " \n"[j == n];
// }
// cout << L << ", " << R << endl;
// system("pause");
cout << R - L + 1 << endl;
}
return 0;
}
/*
Input:
3 5
1 2 3
3 4
2 -2
1 -3
3 1
2 1
Output:
1 2 2 2 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 13920kb
input:
3 5 1 2 3 3 4 2 -2 1 -3 3 1 2 1
output:
1 2 2 2 3
result:
ok 5 number(s): "1 2 2 2 3"
Test #2:
score: 0
Accepted
time: 2ms
memory: 13912kb
input:
3 5 1 2 3 3 4 2 -2 1 3 3 1 2 1
output:
1 2 1 2 1
result:
ok 5 number(s): "1 2 1 2 1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 13920kb
input:
1 1 1000000000 1 1000000000
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: -100
Memory Limit Exceeded
input:
1 1 -1000000000 1 -1000000000