Submission #372653

#	Time	Username	Problem	Language	Result	Execution time	Memory
372653		hohohaha	코알라 (JOI13_koala)	C++14	100 / 100	187 ms	15596 KiB

koala

#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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50