oj.uz

Submission #372653

# Submission time Handle Problem Language Result Execution time Memory
372653 2021-03-01T08:39:10 Z hohohaha 코알라 (JOI13_koala) C++14
100 / 100
 187 ms 15596 KB 
#include<bits/stdc++.h>

using namespace std;

#define loop(i, l, r) for(int i = (int) l; i <= (int) r; i++)
#define rloop(i, r, l) for(int i = (int) r; i >= (int) l; i--)

#define vi vector<int>
#define eb emplace_back
#define ii pair<int, int>
#define fi first
#define se second
#define all(x) begin(x), end(x)

#define rand
#define endl '\n'
#define sp ' '

#define int long long

const int maxN = 2e5, inf = LLONG_MAX / 100ll;

int N; 
int T[maxN], B[maxN], A, K, M, D;
struct 
{
	#define m (l + r) / 2
	#define lc 2 * i, l, m
	#define rc 2 * i + 1, m + 1, r 
	vi mx = vi(4 * maxN, -inf), lz = vi(4 * maxN, 0);
	void pd(int i, int l, int r)
	{
		if(lz[i])
		{
			mx[i] += lz[i];
			if(l < r) lz[2 * i] += lz[i], lz[2 * i + 1] += lz[i];
			lz[i] = 0;
		}
	}
	void add(int i, int l, int r, int ql, int qr, int v)
	{
//		cout << 1 << endl;
		pd(i, l, r);
		if(l > qr or ql > r) return;
		if(ql <= l and r <= qr) 
		{
			lz[i] += v;
			pd(i, l, r);
		}
		else
		{
			add(lc, ql, qr, v);
			add(rc, ql, qr, v);
			mx[i] = max(mx[2 * i], mx[2 * i + 1]);
		}
	}
	int get(int Size)
	{
		pd(1, 1, Size);
		return mx[1];
	}
	void assign(int i, int l, int r, int p, int v)
	{
//		cout << i << sp << l << sp << r << endl;
		pd(i, l, r);
		if(l > p or p > r) return;
		if(l == r) mx[i] = max(mx[i], v);
		else
		{
			assign(lc, p, v);
			assign(rc, p, v);
			mx[i] = max(mx[2 * i], mx[2 * i + 1]);
		}
	}
} IT;

vi Ax;
int gcpr(int x)
{
	return lower_bound(all(Ax), x) - begin(Ax) + 1;
}
int NP;
void add(int d)
{
	int T = d / D;
	d %= D;
	IT.add(1, 1, Ax.size(), 1, Ax.size(), - T * A);
	int i = gcpr(NP), tmp = (NP + d) % D;
	int n = gcpr(tmp);
	if(n == i) return;
	if(n > i)
	{
		IT.add(1, 1, Ax.size(), i, n - 1, -A);
	}
	else
	{
		IT.add(1, 1, Ax.size(), i, Ax.size(), -A);
		if(n > 1) IT.add(1, 1, Ax.size(), 1, n - 1, -A);
	}
	NP = tmp;
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> K >> M >> D >> A >> N;
	T[0] = K, T[N + 1] = M;
	loop(i,1, N)
	{
		cin >> T[i] >> B[i];
	}
	loop(i, 0, N + 1) Ax.eb(T[i] % D);
	sort(all(Ax));
	loop(i, 0, N + 1)
	{
		if(!i) 
		{
			add(T[0]);
//			cout << "done";
			IT.assign(1, 1, Ax.size(), gcpr(T[0] % D), 0);
//			cout << "done";
		}
		else
		{
			add(T[i] - T[i - 1]);
			int v = IT.get(Ax.size()) + B[i];
			if(i == N + 1) return cout << v, 0;
			IT.assign(1, 1, Ax.size(), gcpr(NP % D), v);
		}
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 8 ms 12908 KB Output is correct
3 Correct 8 ms 12908 KB Output is correct
4 Correct 8 ms 12908 KB Output is correct
5 Correct 8 ms 12908 KB Output is correct
6 Correct 9 ms 12908 KB Output is correct
7 Correct 8 ms 12908 KB Output is correct
8 Correct 8 ms 12908 KB Output is correct
9 Correct 9 ms 12908 KB Output is correct
10 Correct 9 ms 12908 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 15596 KB Output is correct
2 Correct 148 ms 15596 KB Output is correct
3 Correct 52 ms 14576 KB Output is correct
4 Correct 158 ms 15596 KB Output is correct
5 Correct 90 ms 14448 KB Output is correct
6 Correct 58 ms 14064 KB Output is correct
7 Correct 71 ms 15596 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 15596 KB Output is correct
2 Correct 175 ms 15596 KB Output is correct
3 Correct 143 ms 15596 KB Output is correct
4 Correct 114 ms 15596 KB Output is correct
5 Correct 108 ms 14448 KB Output is correct
6 Correct 81 ms 14320 KB Output is correct