Submission #72401121

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2e5 + 5;
int a[N],b[N];
long long sum_1,sum_2,cnt_2,best;
multiset<int> set_1,set_2,yes,no;

void balance()
{
	while(yes.size() > cnt_2) 
	{
		best -= *yes.begin();
		no.insert(*yes.begin());
		yes.erase(yes.begin());
	}
	while(!no.empty() && yes.size() < cnt_2)
	{
	    best += *no.rbegin();
	    yes.insert(*no.rbegin());
	    no.erase(--no.end());
	}
}

void insert(int p)
{
    if(b[p] == 1)
    {
        set_1.insert(a[p]);
        sum_1 += a[p];
    }
    else
    {
        set_2.insert(a[p]);
        cnt_2++;
        sum_2 += a[p];
    }
    if(no.empty() || a[p] > (*no.rbegin()))
    {
        yes.insert(a[p]);
        best += a[p];
    }
    else
    {
        no.insert(a[p]);
    }
    balance();
}

void erase(int p)
{
    if(b[p] == 1)
    {
        set_1.erase(set_1.find(a[p]));
        sum_1 -= a[p];
    }
    else
    {
        set_2.erase(set_2.find(a[p]));
        cnt_2--;
        sum_2 -= a[p];
    }
    if(no.empty() || a[p] > (*no.rbegin()))
    {
        yes.erase(yes.find(a[p]));
        best -= a[p];
    }
    else
    {
        no.erase(no.find(a[p]));
    }
    balance();
}

long long calc()
{
    if(set_2.empty())
    {
        return sum_1;
    }
    else if(set_1.empty())
    {
        return ((sum_2 - *set_2.begin()) << 1) + *set_2.begin();
    }
    else if(*set_1.rbegin() < *set_2.begin())
    {
        return ((sum_2 - *set_2.begin() + *set_1.rbegin()) << 1) + sum_1 - *set_1.rbegin() + *set_2.begin();
    }
    else
    {
        return (best << 1) + sum_2 + sum_1 - best;
    }
}

signed main()
{
	int n,q;
	scanf("%lld %lld",&n,&q);
	for(int i = 1;i <= n;i++)
	{
	    scanf("%lld %lld",&a[i],&b[i]);
	    insert(i);
	}
	while(q--)
	{
	    int p,x,y;
	    scanf("%lld %lld %lld", &p, &x, &y);
	    erase(p);
	    a[p] = x;
	    b[p] = y;
	    insert(p);
	    printf("%lld\n",calc());
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'void balance()':
./Main.cpp:12:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   12 |         while(yes.size() > cnt_2)
      |               ~~~~~~~~~~~^~~~~~~
./Main.cpp:18:41: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   18 |         while(!no.empty() && yes.size() < cnt_2)
      |                              ~~~~~~~~~~~^~~~~~~

Judge Result