QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#713647 | #7787. Maximum Rating | surenjamts | WA | 3ms | 53744kb | C++17 | 3.9kb | 2024-11-05 20:09:37 | 2024-11-05 20:09:37 |
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 = 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'