QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#63293 | #4636. Optimal Assortment | Yansuan_HCl | TL | 0ms | 0kb | C++14 | 2.7kb | 2022-11-21 15:43:08 | 2022-11-21 15:43:09 |
Judging History
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