QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#716747 | #7787. Maximum Rating | surenjamts | ML | 2ms | 22380kb | C++17 | 3.4kb | 2024-11-06 15:57:54 | 2024-11-06 15:57:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define F first
#define S second
const int N = 200045;
int h[2*N];
bool arr[N], ex[2*N];
int tree[8*N], ztree[8*N];
vector <int> v;
void build( int l, int r, int node ){
if( l == r ){
if( ex[ l ] ){
tree[node] = v[l];
}else
ztree[node] = 1;
return;
}
int mid = (l+r)/2;
build( l, mid, node*2 );
build( mid+1,r, node*2+1 );
tree[node] = tree[node*2]+tree[node*2+1];
ztree[node] = ztree[node*2]+ztree[node*2+1];
}
void add( int l, int r, int node, int idx ){
if( idx < l || r < idx )
return;
if( l == r ){
tree[node] = v[l];
ztree[node] = 0;
return;
}
int mid = (l+r)/2;
add( l, mid, node*2, idx );
add( mid+1, r, node*2+1, idx );
tree[node] = tree[node*2]+tree[node*2+1];
ztree[node] = ztree[node*2]+ztree[node*2+1];
}
void delet( int l, int r, int node, int idx ){
if( idx < l || r < idx )
return;
if( l == r ){
tree[node] = 0;
ztree[node] = 1;
return;
}
int mid = (l+r)/2;
delet( l, mid, node*2, idx );
delet( mid+1, r, node*2+1, idx );
tree[node] = tree[node*2]+tree[node*2+1];
ztree[node] = ztree[node*2]+ztree[node*2+1];
}
int get_sum( int l, int r, int L, int R, int node ){
if( r < L || R < l ){
return 0;
}
if( L <= l && r <= R ){
return tree[node];
}
int mid = (l+r)/2;
return get_sum( l, mid, L, R, node*2 ) + get_sum( mid+1, r, L, R, node*2+1 );
}
int get_zero( int l, int r, int L, int R, int node ){
if( r < L || R < l ){
return 0;
}
if( L <= l && r <= R ){
return ztree[node];
}
int mid = (l+r)/2;
return get_zero( l, mid, L, R, node*2 ) + get_zero( mid+1, r, L, R, node*2+1 );
}
signed main(){
int n, q, a[N], b[N];
cin >> n >> q;
int H = 1, neg_sum = 0;
vector <pair<int,int>> vc;
vc.pb( {-1,-1} );
v.pb( -1 );
for(int i = 1; i <= n; i ++ ){
cin >> a[i];
if( a[i] > 0 ){
arr[ H ] = 1;
b[ i ] = H;
vc.pb( {a[i],H++} );
}else{
b[i] = a[i];
neg_sum += a[i];
}
}
pair < int, int > p[N];
int query_idx[2*N];
for(int i = 1; i <= q; i ++ ){
cin >> p[i].F >> p[i].S;
if( p[i].S > 0 ){
query_idx[i] = H;
vc.pb( {p[i].S, H++} );
}
}
sort( vc.begin(), vc.end() );
int id[2*N];
for(int i = 1; i < vc.size(); i ++ ){
v.pb( vc[i].F );
if( arr[ vc[i].S ] ){
ex[ i ] = 1;
}
id[ vc[i].S ] = i;
}
for(int i = 1; i <= n; i ++ ){
if( b[i] > 0 ){
b[i] = id[ b[i] ];
}
}
int all = vc.size()-1;
build( 1, all, 1 );
for(int i = 1; i <= q; i ++ ){
// cout << "deleted: " << b[ p[i].F ] << " ";
if( b[ p[i].F ] <= 0 ){
neg_sum -= b[ p[i].F ];
}else{
delet( 1, all, 1, b[ p[i].F ] );
}
// cout << "added: ";
if( p[i].S <= 0 ){
// cout << p[i].S << "\n";
neg_sum += p[i].S;
b[ p[i].F ] = p[i].S;
}else{
// cout << id[ query_idx[i] ] << "\n";
add( 1, all, 1, id[ query_idx[i] ] );
b[ p[i].F ] = id[ query_idx[i] ];
}
int l = 1, r = all;
int k = 0;
// cout << "ANS_IDX" << i << "\n";
while( l <= r ){
int mid = (l+r)/2;
// cout << l << " " << r << "\n";
// cout << "mid:" << mid << " sum:" << get_sum(1,all,1,mid,1) << " zero:" << get_zero(1,all,1,mid,1) << "\n";
if( get_sum( 1, all, 1, mid, 1 ) <= -neg_sum ){
k = mid - get_zero( 1, all, 1, mid, 1 );
l = mid+1;
}else{
r = mid-1;
}
}
cout << k+1 << "\n";
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 22244kb
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: 22380kb
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: 20200kb
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