oj.uz

Submission #43158

# Submission time Handle Problem Language Result Execution time Memory
43158 2018-03-09T16:09:45 Z ffresh 코알라 (JOI13_koala) C++14
100 / 100
 215 ms 9208 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(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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 4 ms 3552 KB Output is correct
3 Correct 4 ms 3604 KB Output is correct
4 Correct 3 ms 3604 KB Output is correct
5 Correct 5 ms 3676 KB Output is correct
6 Correct 4 ms 3684 KB Output is correct
7 Correct 4 ms 3684 KB Output is correct
8 Correct 4 ms 3684 KB Output is correct
9 Correct 4 ms 3684 KB Output is correct
10 Correct 4 ms 3684 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4400 KB Output is correct
2 Correct 61 ms 4520 KB Output is correct
3 Correct 25 ms 4520 KB Output is correct
4 Correct 61 ms 4588 KB Output is correct
5 Correct 39 ms 4588 KB Output is correct
6 Correct 30 ms 4588 KB Output is correct
7 Correct 40 ms 4588 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 7532 KB Output is correct
2 Correct 201 ms 9068 KB Output is correct
3 Correct 215 ms 9196 KB Output is correct
4 Correct 131 ms 9208 KB Output is correct
5 Correct 138 ms 9208 KB Output is correct
6 Correct 79 ms 9208 KB Output is correct