QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#716747#7787. Maximum RatingsurenjamtsML 2ms22380kbC++173.4kb2024-11-06 15:57:542024-11-06 15:57:54

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 15:57:54]
  • 评测
  • 测评结果:ML
  • 用时:2ms
  • 内存:22380kb
  • [2024-11-06 15:57:54]
  • 提交

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

output:


result: