QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#63293#4636. Optimal AssortmentYansuan_HClTL 0ms0kbC++142.7kb2022-11-21 15:43:082022-11-21 15:43:09

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-21 15:43:09]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2022-11-21 15:43:08]
  • Submitted

answer

#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il inline
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
template <typename T> using BS = basic_string<T>;

const int SZ(1 << 22);
unsigned char buf[SZ], *S, *Q;
#define getchar() ((S==Q)&&(Q=buf+fread(S=buf,1,SZ,stdin)),S==Q?EOF:*S++)
template <typename T>
void rd(T& s) {
	int c = getchar();
	T f = 1; s = 0;
	while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); }
	while (isdigit(c)) { s = s * 10 + (c ^ 48); c = getchar(); }
	s *= f;
}
template <typename T, typename... Y>
void rd(T& x, Y&... y) { rd(x), rd(y...); }
#define meow(...) fprintf(stderr, __VA_ARGS__)

const int N = 200005;
using ld = double;

struct Node { ll sL, sVL; };
il Node operator + (Node l, Node r) {
	return {l.sL + r.sL, l.sVL + r.sVL}; }
struct T {
	const static int V = 1000006;
	// iLi,Li
	Node tr[V << 2];
	#define mid ((l + r) >> 1)
	#define LS (p << 1)
	#define RS (LS | 1)
	#define ARG int p = 1, int l = 0, int r = 1e6
	void add(int x, ll v, ARG) {
		if (l == r) {
			tr[p].sL += v;
			tr[p].sVL += v * x;
			return;
		}
		if (x <= mid) add(x, v, LS, l, mid);
		else add(x, v, RS, mid + 1, r);
		tr[p] = tr[LS] + tr[RS];
	}
	int search(ll c, ll cL, ll cVL, ARG) {
		if (l == r) return l;
		ll ra = tr[RS].sVL + cVL - (cL + tr[RS].sL) * mid;
		if (ra <= c * mid) return // r = mid
			search(c, cL + tr[RS].sL, cVL + tr[RS].sVL, LS, l, mid);
		else return
			search(c, cL, cVL, RS, mid + 1, r);			
	}
	Node query(int b, int e, ARG) {
		if (b <= l && e >= r) return tr[p];
		if (b <= mid && e > mid) return
			query(b, e, LS, l, mid) + query(b, e, RS, mid + 1, r);
		if (b <= mid) return query(b, e, LS, l, mid);
		else return query(b, e, RS, mid + 1, r);
	}
} tr;

int n, m, v[N], l[N], r[N];
ll C;

void ask() {
//	if (!C)
//		meow("Break");
	if (!tr.query(0, 1e6).sVL) {
		puts("0/1");
		return;
	}
	int p = tr.search(C, 0, 0);
//	clog << p << ' ' << C << endl;
//	U (i, 1, n) clog << v[i] << ' '; clog << endl;
//	U (i, 1, n) clog << l[i] << ' '; clog << endl;
	
	Node nd = tr.query(p, 1e6);
	ll a = nd.sVL, b = C + nd.sL, g = __gcd(a, b);
	a /= g; b /= g;
	if (!a) b = 1;
	printf("%lld/%lld\n", a, b);
}

int main() {	
	rd(n, m);
	U (i, 1, n) rd(v[i]);
	U (i, 0, n) rd(l[i]);
	U (i, 0, n) rd(r[i]);
	C = r[0];
	U (i, 1, n) tr.add(v[i], l[i]);	
	ask();
	
	U (i, 1, m) {
		int t, x, y, z; rd(t, x, y, z);
		if (t) {
			tr.add(v[t], y - l[t]);
			l[t] = y;
			if (x != v[t]) {
				tr.add(v[t], -l[t]);
				tr.add(x, l[t]);
				v[t] = x;
			}
		} else {
			C = z;
		}
		ask();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

2 5
4 2
4 3 2
4 3 2
2 1 2
1 1 2 3
1 0 0 0
1 1 0 0
1 2 0 0

output:


result: