QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#368632 | #4636. Optimal Assortment | hos_lyric | AC ✓ | 231ms | 45020kb | C++14 | 8.3kb | 2024-03-27 14:34:13 | 2024-03-27 14:34:57 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
// T: monoid representing information of an interval.
// T() should return the identity.
// T(S s) should represent a single element of the array.
// T::pull(const T &l, const T &r) should pull two intervals.
template <class T> struct SegmentTreePoint {
int logN, n;
vector<T> ts;
SegmentTreePoint() : logN(0), n(0) {}
explicit SegmentTreePoint(int n_) {
for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
ts.resize(n << 1);
}
template <class S> explicit SegmentTreePoint(const vector<S> &ss) {
const int n_ = ss.size();
for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
ts.resize(n << 1);
for (int i = 0; i < n_; ++i) at(i) = T(ss[i]);
build();
}
T &at(int i) {
return ts[n + i];
}
void build() {
for (int u = n; --u; ) pull(u);
}
inline void pull(int u) {
ts[u].pull(ts[u << 1], ts[u << 1 | 1]);
}
// Changes the value of point a to s.
template <class S> void change(int a, const S &s) {
assert(0 <= a); assert(a < n);
ts[a += n] = T(s);
for (; a >>= 1; ) pull(a);
}
// Applies T::f(args...) to point a.
template <class F, class... Args>
void ch(int a, F f, Args &&... args) {
assert(0 <= a); assert(a < n);
(ts[a += n].*f)(args...);
for (; a >>= 1; ) pull(a);
}
// Calculates the product for [a, b).
T get(int a, int b) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return T();
T prodL, prodR, t;
for (a += n, b += n; a < b; a >>= 1, b >>= 1) {
if (a & 1) { t.pull(prodL, ts[a++]); prodL = t; }
if (b & 1) { t.pull(ts[--b], prodR); prodR = t; }
}
t.pull(prodL, prodR);
return t;
}
// Calculates T::f(args...) of a monoid type for [a, b).
// op(-, -) should calculate the product.
// e() should return the identity.
template <class Op, class E, class F, class... Args>
#if __cplusplus >= 201402L
auto
#else
decltype((std::declval<T>().*F())())
#endif
get(int a, int b, Op op, E e, F f, Args &&... args) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return e();
auto prodL = e(), prodR = e();
for (a += n, b += n; a < b; a >>= 1, b >>= 1) {
if (a & 1) prodL = op(prodL, (ts[a++].*f)(args...));
if (b & 1) prodR = op((ts[--b].*f)(args...), prodR);
}
return op(prodL, prodR);
}
// Find min b s.t. T::f(args...) returns true,
// when called for the partition of [a, b) from left to right.
// Returns n + 1 if there is no such b.
template <class F, class... Args>
int findRight(int a, F f, Args &&... args) {
assert(0 <= a); assert(a <= n);
if ((T().*f)(args...)) return a;
if (a == n) return n + 1;
a += n;
for (; ; a >>= 1) if (a & 1) {
if ((ts[a].*f)(args...)) {
for (; a < n; ) {
if (!(ts[a <<= 1].*f)(args...)) ++a;
}
return a - n + 1;
}
++a;
if (!(a & (a - 1))) return n + 1;
}
}
// Find max a s.t. T::f(args...) returns true,
// when called for the partition of [a, b) from right to left.
// Returns -1 if there is no such a.
template <class F, class... Args>
int findLeft(int b, F f, Args &&... args) {
assert(0 <= b); assert(b <= n);
if ((T().*f)(args...)) return b;
if (b == 0) return -1;
b += n;
for (; ; b >>= 1) if ((b & 1) || b == 2) {
if ((ts[b - 1].*f)(args...)) {
for (; b <= n; ) {
if (!(ts[(b <<= 1) - 1].*f)(args...)) --b;
}
return b - n - 1;
}
--b;
if (!(b & (b - 1))) return -1;
}
}
}; // SegmentTreePoint<T>
////////////////////////////////////////////////////////////////////////////////
/*
ans = max[S] min[w: L[i]<=w[i]<=R[i]] (\sum[i\in S] w[i] V[i]) / (w[0] + \sum[i\in S] w[i])
ans >= t possible?
\forall w, \sum[i\in S] w[i] (V[i] - t) >= w[0] t
consider only:
w[0] = R[0]
w[i] = L[i]
S = {i | V[i] >= t}
\sum L[i] V[i] >= (R[0] + \sum[i] L[i]) t
0/0 case: max V[i] s.t. L[i] > 0
*/
constexpr Int INF = 1001001001001001001LL;
struct Node {
Int sumLV, sumL, minV;
Node() : sumLV(0), sumL(0), minV(INF) {}
Node(Int v, Int l) : sumLV(l * v), sumL(l), minV(v) {}
void pull(const Node &l, const Node &r) {
sumLV = l.sumLV + r.sumLV;
sumL = l.sumL + r.sumL;
minV = min(l.minV, r.minV);
}
bool testEasy() const {
return (sumL > 0);
}
bool testHard(Int &lv, Int &l, Int &t) const {
const Int lvlv = lv + sumLV;
const Int ll = l + sumL;
const Int tt = min(t, minV);
if (tt < INF && lvlv >= ll * tt) return true;
lv = lvlv;
l = ll;
t = tt;
return false;
}
};
int N, Q;
vector<Int> V;
vector<Int> L;
Int R;
vector<int> O;
vector<int> X;
vector<Int> LL, RR, VV;
SegmentTreePoint<Node> seg;
void solve() {
// cerr<<"[solve] V = "<<V<<", L = "<<L<<", R = "<<R<<endl;
Int p = 0, q = 1;
if (R == 0) {
const int pos = seg.findLeft(seg.n, &Node::testEasy);
if (pos >= 0) {
p = seg.at(pos).minV;
q = 1;
}
} else {
Int lv = 0, l = R, t = INF;
const int pos = seg.findLeft(seg.n, &Node::testHard, lv, l, t);
// cerr<<" pos = "<<pos<<", lv = "<<lv<<", l = "<<l<<", t = "<<t<<endl;
p = lv;
q = l;
}
const Int g = __gcd(p, q);
p /= g;
q /= g;
printf("%lld/%lld\n", p, q);
}
int main() {
for (; ~scanf("%d%d", &N, &Q); ) {
V.resize(N);
for (int i = 0; i < N; ++i) scanf("%lld", &V[i]);
L.resize(N);
scanf("%*lld");
for (int i = 0; i < N; ++i) scanf("%lld", &L[i]);
scanf("%lld", &R);
for (int i = 0; i < N; ++i) scanf("%*lld");
O.assign(Q, 0);
X.assign(Q, -2);
LL.assign(Q, 0);
RR.assign(Q, 0);
VV.assign(Q, 0);
for (int q = 0; q < Q; ++q) {
scanf("%d%d", &O[q], &X[q]);
--X[q];
if (O[q] == 1) {
scanf("%lld%lld", &LL[q], &RR[q]);
} else if (O[q] == 2) {
scanf("%lld", &VV[q]);
} else {
assert(false);
}
}
vector<pair<Int, int>> ps;
for (int i = 0; i < N; ++i) ps.emplace_back(V[i], i);
for (int q = 0; q < Q; ++q) if (O[q] == 2) ps.emplace_back(VV[q], N + q);
sort(ps.begin(), ps.end());
const int psLen = ps.size();
// cerr<<"ps = "<<ps<<endl;
vector<int> poss(N);
seg = SegmentTreePoint<Node>(psLen);
for (int i = 0; i < N; ++i) {
poss[i] = lower_bound(ps.begin(), ps.end(), make_pair(V[i], i)) - ps.begin();
seg.at(poss[i]) = Node(V[i], L[i]);
}
seg.build();
solve();
for (int q = 0; q < Q; ++q) {
const int i = X[q];
if (O[q] == 1) {
if (~i) {
L[i] = LL[q];
seg.change(poss[i], Node(V[i], L[i]));
} else {
R = RR[q];
}
} else if (O[q] == 2) {
seg.change(poss[i], Node());
poss[i] = lower_bound(ps.begin(), ps.end(), make_pair(VV[q], N + q)) - ps.begin();
V[i] = VV[q];
seg.change(poss[i], Node(V[i], L[i]));
} else {
assert(false);
}
solve();
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3772kb
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:
16/9 10/9 1/1 2/1 2/1 0/1
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 210ms
memory: 42988kb
input:
200000 200000 959139 199252 470888 74578 802746 396295 386884 721198 628655 722503 207868 647942 87506 792718 761498 917727 843338 908043 952768 268783 375312 414369 319712 96230 277106 168102 263554 936674 246545 667941 198849 268921 191459 436316 134606 802932 515506 837311 465964 394766 17626 650...
output:
311567211361053/313072603 311567211361053/313072603 311567211361053/313072603 311567211361053/313072603 311567211361053/313072603 311567211361053/313072603 311567211361053/313072603 311567211361053/313072603 311567211361053/313072603 311567211361053/313072603 311567211361053/313072603 31156721136105...
result:
ok 200001 lines
Test #3:
score: 0
Accepted
time: 231ms
memory: 43584kb
input:
200000 200000 9859 748096 475634 928248 927808 875072 158867 937890 595515 26685 468307 240390 887597 586447 764525 365644 156469 188306 350786 308832 695957 562147 427221 937909 590963 478310 357775 361535 993561 967811 718075 555000 533750 412453 936715 173340 350235 67386 20497 895277 233727 2358...
output:
103848766309007/104372723 103848766309007/104372723 103848766309007/104372723 103848766309007/104372723 103848766309007/104372723 103848766309007/104372723 103848766309007/104372723 103848766309007/104372723 103848766309007/104372723 103848766309007/104372723 103848766309007/104372723 10384876630900...
result:
ok 200001 lines
Test #4:
score: 0
Accepted
time: 221ms
memory: 43396kb
input:
200000 200000 125987 264237 288891 590429 244358 321145 930851 89174 529670 363571 728747 543238 720391 188689 702144 813561 628383 660056 781508 605777 759705 485733 534730 812292 937524 788519 451996 10588 483682 267682 461493 65270 619145 355885 963015 800644 217669 264757 640439 685387 674020 85...
output:
164953272455879/165821396 164953272455879/165821396 164953272455879/165821396 164953272455879/165821396 164953272455879/165821396 164953272455879/165821396 164953272455879/165821396 164953272455879/165821396 164953272455879/165821396 164953272455879/165821396 164953272455879/165821396 16495327245587...
result:
ok 200001 lines
Test #5:
score: 0
Accepted
time: 200ms
memory: 43712kb
input:
200000 200000 139 252 888 578 746 295 884 198 655 503 868 942 506 718 498 727 338 43 768 783 312 369 712 230 106 102 554 674 545 941 849 921 459 316 606 932 506 311 964 766 626 419 50 137 79 900 340 81 277 815 250 183 862 825 976 927 448 966 261 146 4 178 996 461 128 564 181 920 206 286 909 304 755 ...
output:
500000000000/500427 341515459/343039 341515459/343039 341515459/343039 341515459/343039 500000000000/500427 500000000000/500427 500000000000/500427 500000000000/500427 341515459/343039 341515459/343039 341515459/343039 341515459/343039 500000000000/500427 500000000000/500427 500000000000/500427 5000...
result:
ok 200001 lines
Test #6:
score: 0
Accepted
time: 218ms
memory: 44920kb
input:
200000 200000 859 96 634 248 808 72 867 890 515 685 307 390 597 447 525 644 469 306 786 832 957 147 221 909 963 310 775 535 561 811 75 1000 750 453 715 340 235 386 497 277 727 830 535 591 972 687 856 325 895 770 660 722 147 349 168 161 335 587 116 654 220 91 35 739 864 121 158 44 805 420 561 387 66 ...
output:
1000000000000/1000901 322131723/323698 322131723/323698 322131723/323698 322131723/323698 1000000000000/1000901 1000000000000/1000901 1000000000000/1000901 1000000000000/1000901 322131723/323698 322131723/323698 322131723/323698 322131723/323698 1000000000000/1000901 1000000000000/1000901 1000000000...
result:
ok 200001 lines
Test #7:
score: 0
Accepted
time: 218ms
memory: 45020kb
input:
200000 200000 987 237 891 429 358 145 851 174 670 571 747 238 391 689 144 561 383 56 508 777 705 733 730 292 524 519 996 588 682 682 493 270 145 885 15 644 669 757 439 387 20 944 420 750 968 67 771 865 809 941 286 478 433 465 64 100 926 912 971 266 923 413 370 825 87 487 647 168 596 258 110 877 81 2...
output:
62500000000/62553 325796648/327289 325796648/327289 325796648/327289 325796648/327289 62500000000/62553 62500000000/62553 62500000000/62553 62500000000/62553 325796648/327289 325796648/327289 325796648/327289 325796648/327289 62500000000/62553 62500000000/62553 62500000000/62553 62500000000/62553 32...
result:
ok 200001 lines
Test #8:
score: 0
Accepted
time: 135ms
memory: 43900kb
input:
200000 200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1000000000000/1520839 7411875116/7411932987 1000000000000/1520839 66705876044/66706396883 1000000000000/1520839 7411875116/7411932987 1000000000000/1520839 66705876044/66706396883 1000000000000/1520839 7411875116/7411932987 1000000000000/1520839 66705876044/66706396883 1000000000000/1520839 74118751...
result:
ok 200001 lines