oj.uz

Submission #43092

# Submission time Handle Problem Language Result Execution time Memory
43092 2018-03-09T05:31:26 Z ffresh 코알라 (JOI13_koala) C++14
100 / 100
 224 ms 10076 KB 
#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(qr<l || r<ql)return -3e18;

	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));
}

ll x[N],b[N];


int main(){
	//freopen("input.txt","r",stdin);
	ll k,m,d,a,n;

	cin>>k>>m>>d>>a>>n;

	for(int i=0;i<N*4;++i)tree[i] = -3e18;

	map<int,int> Hash;
	ll pos = (k/d);
	ll value = -a*pos;
	
	for(int i=1;i<=n;++i){
		scanf("%lld%lld",&x[i],&b[i]);
		Hash[x[i]%d];
	}
	x[n+1] = m;
	int ind=0,id;
	Hash[k%d];
	Hash[m%d];
	for(map<int,int>::iterator it= Hash.begin();it!= Hash.end();++it){
		it->second = ind++;
	}
	update_ind(1,0,ind-1,Hash[k%d],-value);

	ll q;
	for(int i=1;i<=n+1;++i){
		id = x[i]%d;
		id = Hash[id];
		pos = (x[i]/d);
		value = -a*pos;
		q = -3e18;
		if(id>0){
			q = query(1,0,ind-1,0,id-1)-a;
		}
		q= max(q,query(1,0,ind-1,id,ind-1)) ;
		q += value + b[i];
		update_ind(1,0,ind-1,id,q-value);
	}
	cout<<q<<endl;

}

Compilation message

koala.cpp: In function 'int main()':
koala.cpp:54:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&x[i],&b[i]);
                                ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3448 KB Output is correct
2 Correct 5 ms 3552 KB Output is correct
3 Correct 5 ms 3624 KB Output is correct
4 Correct 4 ms 3624 KB Output is correct
5 Correct 4 ms 3624 KB Output is correct
6 Correct 4 ms 3624 KB Output is correct
7 Correct 4 ms 3624 KB Output is correct
8 Correct 4 ms 3692 KB Output is correct
9 Correct 5 ms 3704 KB Output is correct
10 Correct 4 ms 3720 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 5280 KB Output is correct
2 Correct 64 ms 5280 KB Output is correct
3 Correct 28 ms 5280 KB Output is correct
4 Correct 65 ms 5280 KB Output is correct
5 Correct 46 ms 5280 KB Output is correct
6 Correct 24 ms 5280 KB Output is correct
7 Correct 34 ms 5280 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 8336 KB Output is correct
2 Correct 224 ms 9760 KB Output is correct
3 Correct 193 ms 10076 KB Output is correct
4 Correct 136 ms 10076 KB Output is correct
5 Correct 129 ms 10076 KB Output is correct
6 Correct 86 ms 10076 KB Output is correct