QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#713647#7787. Maximum RatingsurenjamtsWA 3ms53744kbC++173.9kb2024-11-05 20:09:372024-11-05 20:09:37

Judging History

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

  • [2024-11-05 20:09:37]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:53744kb
  • [2024-11-05 20:09:37]
  • 提交

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 = 400045;
map<int,int> mp,mpp;
bool tmp[2*N], ex[N*2], og[N];
int tree[N*8], ztree[N*8], lst[2*N];
vector <int> v;
void build( int l, int r, int node ){
	if( r < l )
		return;
	if( l == r ){
		if( ex[l] ){
			tree[node] = v[l];
		}else{
			ztree[node] ++;
		}
		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(){
//	ios_base::sync_with_stdio(NULL);
//	cin.tie(NULL);
//	cout.tie(NULL);
	int n, q, a[N], b[N], m[2*N], mm[2*N], que[2*N], id[2*N];
	cin >> n >> q;
	vector < pair<int,int> > vc, query;
	vc.pb( {-1,-1} );
	v.pb(-1);
	int neg_sum = 0, h = 1;
	int hsh[2*N];
	for(int i = 1; i <= n; i ++ ){
		cin >> a[i];
		b[i] = a[i];
		if( a[i] <= 0 )
			neg_sum += a[i];
		else{
			og[ i ] = 1;
			tmp[h] = 1;
			m[ h ] = i;
			hsh[i] = h;
			vc.pb( {a[i],h++} );
		}
	}
	pair<int,int> p[N];
	for(int i = 1; i <= q; i ++ ){
		cin >> p[i].F >> p[i].S;
		if( p[i].S > 0 ){
			que[ h ] = i;
			vc.pb( {p[i].S,h++} );
		}
	}
	sort( vc.begin(), vc.end() );
	for(int i = 1; i < vc.size(); i ++ ){
		v.pb( vc[i].F );
		if( tmp[vc[i].S] ){
			ex[i] = 1;
			mm[ m[vc[i].S] ] = i;
		}
		else{
			id[que[ vc[i].S ]] = i;
		}
	}
	n = vc.size()-1;
	build( 1, n, 1 );
	int f, s;
	for(int i = 1; i <= q; i ++ ){
		bool gege = false;
		if( b[ p[i].F ] <= 0 ){
			f = b[ p[i].F ];
		}else{
			if( og[ p[i].F ] ){
				og[ p[i].F ] = 0;
				f = mm[hsh[ p[i].F ]];
			}else{
				f = lst[p[i].F];
			}
		}
		if( p[i].S <= 0 ){
			s = p[i].S;
		}else{
			s = id[ i ];
//			cout << "query" << i << ":" << p[i].F << "<-" << s << "\n";
			lst[ p[i].F ] = s;
		}
		
		b[ p[i].F ] = p[i].S;
		query.pb( {f,s} );
	}
//	cout << "tree:\n";
//	for(int i = 1; i <= 9; i ++ ){
//		cout << i << ":" << tree[i] << "\n";
//	}
//	return 0;
	for(int i = 0; i < query.size(); i ++ ){
//		cout << "QUERY" << i+1 << "\n";
//		cout << f << " " << s << "\n";
		int f = query[i].F, s = query[i].S;
		if( f <= 0 ){
			neg_sum -= f;
		}else{
			delet( 1, n, 1, f );
		}
		if( s <= 0 ){
			neg_sum += s;
		}else{
			add( 1, n, 1, s );
		}
		int l = 1, r = n;
		int k = 0;
//		cout << "neg_sum " << neg_sum << "\n";
		while( l < r ){
//			cout << "range:" << l << " " << r << "\n";
			int mid = (l+r)/2;
			if( get_sum( 1,n,1,mid,1 ) <= abs(neg_sum) ){
				k = mid-get_zero(1,n,1,mid,1);
//				cout << mid << " " << get_sum( 1,n,1,mid,1 ) << " " << get_zero(1,n,1,mid,1) << "\n";
				l = mid+1;	
			}else{
				r = mid;
			}
		}
		cout << k+1 << "\n";
	}
}

详细

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 53744kb

input:

3 5
1 2 3
3 4
2 -2
1 -3
3 1
2 1

output:

1
2
1
2
3

result:

wrong answer 3rd numbers differ - expected: '2', found: '1'