Submission #618079

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#define SIZE 100005
#define BT 1024*128*2

using namespace std;
typedef long long int ll;

struct segtree
{
	ll add[BT];///f(i)-f(i+1)を持つ
	bool rm[BT];
	int mum;
	
	void init(int n)
	{
		mum=1;
		while(mum<n) mum<<=1;
		for(int i=0;i<mum*2;i++)
		{
			add[i]=0;
			rm[i]=false;
		}
	}
	void pass(int k)
	{
		if(k*2+2<2*mum)
		{
			if(rm[k])
			{
				rm[k]=false;
				add[k*2+1]=add[k*2+2]=0;
				rm[k*2+1]=rm[k*2+2]=true;
			}
			add[k*2+1]+=add[k];
			add[k*2+2]+=add[k];
			add[k]=0;
		}
	}
	void update(int a,int b,int k,int l,int r,ll v)
	{
		if(b<=l||r<=a) return;
		pass(k);
		if(a<=l&&r<=b) add[k]+=v;
		else
		{
			update(a,b,k*2+1,l,(l+r)/2,v);
			update(a,b,k*2+2,(l+r)/2,r,v);
		}
	}
	void update(int a,int b,ll v)
	{
		update(a,b,0,0,mum,v);
	}
	ll get(int x)//これは広義単調減少になるように調整される
	{
		int l=0,r=mum,k=0;
		while(l+1<r)
		{
			pass(k);
			int m=(l+r)/2;
			if(x<m)
			{
				r=m;
				k=k*2+1;
			}
			else
			{
				l=m;
				k=k*2+2;
			}
		}
		return add[k];
	}
	int position()//初めてgetが0以下になるところを探す
	{
		int l=-1,r=mum;
		while(l+1<r)
		{
			int m=(l+r)/2;
			if(get(m)<=0) r=m;
			else l=m;
		}
		return r;
	}
	void fresh(int a,int b,int k,int l,int r)//範囲を0にする
	{
		if(b<=l||r<=a) return;
		pass(k);
		if(a<=l&&r<=b)
		{
			rm[k]=true;
			add[k]=0;
		}
		else
		{
			fresh(a,b,k*2+1,l,(l+r)/2);
			fresh(a,b,k*2+2,(l+r)/2,r);
		}
	}
	void fresh(int a,int b)
	{
		fresh(a,b,0,0,mum);
	}
};
segtree seg;
ll score0;
vector <int> vec[SIZE];

int main()
{
	int n,L;
	scanf("%d %d",&n,&L);
	seg.init(L+2);
	for(int i=0;i<n;i++)
	{
		int t,p;
		scanf("%d %d",&t,&p);t--;
		vec[t].push_back(p);
	}
	for(int i=0;i<SIZE;i++)
	{
		if(vec[i].empty()) continue;
		for(int j=0;j<vec[i].size();j++)
		{
			int p=vec[i][j];
			score0+=p;
			if(p>0) seg.update(0,p,1);
			seg.update(p,seg.mum,-1);
		}
		int gt=seg.position();
		if(gt<seg.mum) seg.fresh(gt,seg.mum);
		//for(int j=0;j<L;j++) printf("%lld ",seg.get(j));puts("");
	}
	//printf("%lld\n",score0);
	int gt=seg.position();
	ll ret=score0;
	for(int i=0;i<gt;i++) ret-=seg.get(i);
	printf("%lld\n",ret);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:116:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&L);
                      ^
./Main.cpp:121:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&t,&p);t--;
                       ^

Judge Result