oj.uz

답안 #145167

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
145167 2019-08-19T01:51:09 Z gs18103 코알라 (JOI13_koala) C++14
70 / 100
 320 ms 16692 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define LINF 1000000000000000LL
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
 
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
 
int t[101010];
ll b[101010], tree[808080], lazy[808080];
 
void update_lazy(int node, int s, int e) {
	tree[node] = max(lazy[node], tree[node]);
	if(s != e) {
		lazy[node*2] = max(lazy[node*2], lazy[node]);
		lazy[node*2+1] = max(lazy[node*2+1], lazy[node]);
	}
	lazy[node] = -LINF;
}
 
void update_range(int node, int s, int e, int l, int r, ll val) {
	update_lazy(node, s, e);
	if(s > r || e < l) return;
	if(s >= l && e <= r) {
		tree[node] = max(tree[node], val);
		lazy[node*2] = max(lazy[node*2], val);
		lazy[node*2+1] = max(lazy[node*2+1], val);
		return;
	}
	int m = (s + e) / 2;
	update_range(node*2, s, m, l, r, val);
	update_range(node*2+1, m+1, e, l, r, val);
	tree[node] = max(tree[node*2], tree[node*2+1]);
}
 
ll cal(int node, int s, int e, int l, int r) {
	update_lazy(node, s, e);
	if(s > r || e < l) return -LINF;
	if(s >= l && e <= r) return tree[node];
	int m = (s + e) / 2;
	return max(cal(node*2, s, m, l, r), cal(node*2+1, m+1, e, l, r));
}
 
vector <int> num;

int main() {
	int K, m, d, n;
	ll a;
	cin >> K >> m >> d >> a >> n;
	for(int i = 1; i <= n; i++) {
		cin >> t[i] >> b[i];
		t[i] -= K;
		num.eb(t[i]%d);
	}
	num.eb((m-K)%d);
	sort(all(num));
	num.erase(unique(all(num)), num.end());
	for(int i = 0; i < 808080; i++) {
		lazy[i] = -LINF;
		tree[i] = -LINF;
	}
	update_range(1, 0, num.size()-1, 0, 0, 0LL);
	update_range(1, 0, num.size()-1, 1, num.size()-1, -a);
	for(int i = 1; i <= n; i++) {
		int k = lower_bound(all(num), t[i]%d) - num.begin();
		ll val = cal(1, 0, num.size()-1, k, k) + b[i];
		update_range(1, 0, num.size()-1, 0, k, val);
		if(k < num.size()-1) update_range(1, 0, num.size()-1, k+1, num.size()-1, val - a);
	}
	int k = lower_bound(all(num), (m-K)%d) - num.begin();
	cout << cal(1, 0, num.size()-1, k, k) - a * (ll)((m - K) / d);
}

Compilation message

koala.cpp: In function 'int main()':
koala.cpp:71:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(k < num.size()-1) update_range(1, 0, num.size()-1, k+1, num.size()-1, val - a);
      ~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 13048 KB Output is correct
2 Correct 15 ms 13048 KB Output is correct
3 Correct 15 ms 13048 KB Output is correct
4 Correct 14 ms 12924 KB Output is correct
5 Correct 14 ms 13048 KB Output is correct
6 Correct 14 ms 13048 KB Output is correct
7 Correct 13 ms 13048 KB Output is correct
8 Correct 15 ms 13048 KB Output is correct
9 Correct 15 ms 13048 KB Output is correct
10 Correct 15 ms 13048 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 16636 KB Output is correct
2 Correct 191 ms 16404 KB Output is correct
3 Correct 111 ms 15440 KB Output is correct
4 Correct 198 ms 16572 KB Output is correct
5 Correct 127 ms 15384 KB Output is correct
6 Correct 79 ms 14452 KB Output is correct
7 Incorrect 115 ms 15608 KB Output isn't correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 304 ms 16624 KB Output is correct
2 Correct 320 ms 16624 KB Output is correct
3 Correct 307 ms 16692 KB Output is correct
4 Correct 286 ms 16624 KB Output is correct
5 Correct 195 ms 15356 KB Output is correct
6 Correct 148 ms 14708 KB Output is correct