Submission #43158

#	Time	Username	Problem	Language	Result	Execution time	Memory
43158		ffresh	코알라 (JOI13_koala)	C++14	100 / 100	215 ms	9208 KiB

koala

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+15;

#define ll long long

ll tree[N*4];

void update_ind(int pos,int l,int r,int ind,ll upd){
	if(l==r){
		tree[pos]= upd;
		return;
	}
	int mid = (l+r)/2;
	if(ind<=mid)
		update_ind(pos*2,l,mid,ind,upd);
	else
		update_ind(pos*2+1,mid+1,r,ind,upd);

	tree[pos]= max(tree[pos*2],tree[pos*2+1]);
}

ll query(int pos,int l,int r,int ql,int qr){
	if(r<ql || qr<l)return -4e18;

	if(ql<=l && r<=qr)return tree[pos];
	int mid = (l+r)/2;
	return max(query(pos*2,l,mid,ql,qr),query(pos*2+1,mid+1,r,ql,qr));
}

int x[N],b[N];

map<int,int> Hash;
int main(){
	//freopen("input.txt","r",stdin);

	int k,m,d,a,n;
	scanf("%d%d%d%d%d",&k,&m,&d,&a,&n);

	x[0]= k;
	x[n+1]= m;
	for(int i=1;i<=n;++i)scanf("%d%d",&x[i],&b[i]);
	for(int i=0;i<N*4;++i)tree[i]= -4e18;
	for(int i=0;i<=n+1;++i){
		int u = x[i]%d;
		Hash[u];
	}


	int pos=0;
	for(map<int,int>::iterator it= Hash.begin();it!=Hash.end();++it){
		it->second = pos++;
	}
	ll q;
	ll xx,val;
	int id;
	for(int i=0;i<=n+1;++i){
		xx = x[i]/d;
		val = -a*xx;

		xx  = x[i]%d;
		id = Hash[xx];
		if(i==0){
			q = 0;
		}
		else{
			q = -4e18;
			if(id>0)
				q= query(1,0,pos-1,0,id-1) -a;

			q = max(q,query(1,0,pos-1,id,pos-1)); 
				
			q+= val;
			q+=b[i];
		}

		update_ind(1,0,pos-1,id, q-val);
	}
	cout<<q<<endl;
}

Compilation message (stderr)

koala.cpp: In function 'int main()':
koala.cpp:40:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d",&k,&m,&d,&a,&n);
                                    ^
koala.cpp:44:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;++i)scanf("%d%d",&x[i],&b[i]);
                                                ^

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50