QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#634389 | #7787. Maximum Rating | NIGHTLOS | RE | 1ms | 8016kb | C++17 | 3.2kb | 2024-10-12 17:12:35 | 2024-10-12 17:12:36 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int N = 4e5 + 5, INF = 1e9 + 5;
const ll MaxN = 1e18;
int n, q;
int a[N];
struct node
{
int l, r;
ll sum, v, cnt;
}tr[N * 10];
struct option
{
int x, v;
}op[N];
ll sum; //负数的和
vector<int> nums;
int find(int x)
{
return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
void pushup(int p)
{
tr[p].cnt = tr[p * 2].cnt + tr[p * 2 + 1].cnt;
tr[p].sum = tr[p * 2].sum + tr[p * 2 + 1].sum;
}
void build(int p, int l, int r)
{
tr[p].l = l; tr[p].r = r;
if(l == r)
{
tr[p].v = nums[l];
tr[p].sum = 0;
tr[p].cnt = 0;
return;
}
int mid = (l + r) / 2;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
pushup(p);
}
void update(int p, int x, int d)
{
if(tr[p].l == tr[p].r)
{
tr[p].cnt += d;
tr[p].sum = tr[p].cnt * tr[p].v;
return;
}
int mid = (tr[p].l + tr[p].r) / 2;
if(mid >= x) update(p * 2, x, d);
else update(p * 2 + 1, x, d);
pushup(p);
}
ll query(int p, int l, int r)
{
if(r == 0) return -MaxN;
if(tr[p].l >= l && tr[p].r <= r)
return tr[p].sum;
int mid = (tr[p].l + tr[p].r) / 2;
ll res = 0;
if(mid >= l) res += query(p * 2, l, r);
if(mid < r) res += query(p * 2 + 1, l, r);
return res;
}
int query_pos(int p, int l, int r)
{
if(r == 0) return 0;
if(tr[p].l >= l && tr[p].r <= r) return tr[p].cnt;
int mid = (tr[p].l + tr[p].r) / 2;
int res = 0;
if(mid >= l) res += query_pos(p * 2, l, r);
if(mid < r) res += query_pos(p * 2 + 1, l, r);
return res;
}
int get(ll d)
{
int ans;
int l = 0, r = nums.size() - 1;
while(l <= r)
{
int mid = (l + r) / 2;
if(query(1, 1, mid) + d <= 0)
{
ans = query_pos(1, 1, mid);
l = mid + 1;
}else
{
r = mid - 1;
}
}
return ans;
}
signed main()
{
nums.push_back(-INF);
scanf("%lld%lld", &n, &q);
for(int i = 1; i <= n; i ++ )
{
scanf("%lld", &a[i]);
if(a[i] > 0) nums.push_back(a[i]);
if(a[i] < 0) sum += a[i];
}
for(int i = 1; i <= q; i ++ )
{
int x, v;
scanf("%lld%lld", &x, &v);
if(v > 0) nums.push_back(v);
op[i] = {x, v};
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
build(1, 1, nums.size() - 1);
for(int i = 1; i <= n; i ++ )
{
if(a[i] > 0)
update(1, find(a[i]), 1);
}
for(int i = 1; i <= q; i ++ )
{
int x = op[i].x, v = op[i].v;
if(a[x] > 0)
{
update(1, find(a[x]), -1ll);
}else
{
sum -= a[x];
}
if(v > 0)
{
update(1, find(v), 1ll);
}else
{
sum += v;
}
a[x] = v;
int t = get(sum);
//cout<<sum<<"***"<<endl;
printf("%lld\n", t + 1ll);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 8008kb
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: 1ms
memory: 8016kb
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: 0ms
memory: 8016kb
input:
1 1 1000000000 1 1000000000
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: -100
Runtime Error
input:
1 1 -1000000000 1 -1000000000