QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#117882 | #6675. DS Team Selection 2 | willow | WA | 2ms | 22836kb | C++14 | 4.9kb | 2023-07-02 12:51:13 | 2023-07-02 12:51:15 |
Judging History
answer
#include<bits/stdc++.h>
#define lc (rt << 1)
#define rc (rt << 1) | 1
using namespace std;
const int MAXN = 200005;
typedef long long LL;
const int B = 450;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, q, tot, vis[MAXN], type[MAXN], ql[MAXN], qr[MAXN];
LL a[MAXN], qv[MAXN];
vector<int> ins[MAXN];
struct Line {
int id;
LL k, b;
inline LL val(LL x) {
return k * x + b;
}
} line[MAXN], stk[MAXN];
int top;
inline bool Check(Line a, Line b, Line c) {
return ((a.b - c.b) * (b.k - a.k) <= (a.b - b.b) * (c.k - a.k));
}
struct BIT {
LL tr[MAXN];
void add(int x, LL v) {
for (; x <= n; x += (x & (-x))) {
tr[x] += v;
}
}
LL sum(int x) {
LL ret = 0;
for (; x; x -= (x & (-x))) {
ret += tr[x];
}
return ret;
}
LL qry(int l, int r) {
return sum(r) - sum(l - 1);
}
} bit1, bit2;
struct Node {
int mx;
LL icnt, isum, vsum, itsum;
};
struct SegmentTree {
LL vtag[MAXN << 2], ttag[MAXN << 2];
Node seg[MAXN << 2];
inline Node Merge(Node x, Node y) {
Node z;
z.mx = max(x.mx, y.mx);
z.icnt = x.icnt + y.icnt;
z.isum = x.isum + y.isum;
z.vsum = x.vsum + y.vsum;
z.itsum = x.itsum + y.itsum;
return z;
}
inline void puttag(int rt, LL vtg, LL ttg) {
vtag[rt] = vtg;
ttag[rt] = ttg;
seg[rt].vsum = seg[rt].icnt * vtg;
seg[rt].itsum = seg[rt].isum * ttg;
}
inline void pushdown(int rt) {
if (vtag[rt] && ttag[rt]) {
puttag(lc, vtag[rt], ttag[rt]);
puttag(rc, vtag[rt], ttag[rt]);
vtag[rt] = ttag[rt] = 0;
}
}
void Insert(int rt, int b, int e, int p, LL v, LL t) {
if (b == e) {
seg[rt].mx = p;
seg[rt].icnt = 1;
seg[rt].isum = p;
seg[rt].vsum = v;
seg[rt].itsum = t * p;
return;
}
int mid = (b + e) >> 1;
pushdown(rt);
if (p <= mid) Insert(lc, b, mid, p, v, t);
else Insert(rc, mid + 1, e, p, v, t);
seg[rt] = Merge(seg[lc], seg[rc]);
}
void Cover(int rt, int b, int e, int l, int r, LL v, LL t) {
if (l <= b && e <= r) {
puttag(rt, v, t);
return;
}
int mid = (b + e) >> 1;
pushdown(rt);
if (l <= mid) Cover(lc, b, mid, l, r, v, t);
if (r > mid) Cover(rc, mid + 1, e, l, r, v, t);
seg[rt] = Merge(seg[lc], seg[rc]);
}
LL Ask(int rt, int b, int e, int p) {
if (b == e) {
if (!seg[rt].icnt) return INF;
return seg[rt].vsum - seg[rt].itsum;
}
int mid = (b + e) >> 1;
pushdown(rt);
if (seg[lc].mx >= p) return Ask(lc, b, mid, p);
else return Ask(rc, mid + 1, e, p);
}
Node Query(int rt, int b, int e, int l, int r) {
if (l <= b && e <= r) return seg[rt];
int mid = (b + e) >> 1;
pushdown(rt);
if (r <= mid) return Query(lc, b, mid, l, r);
if (l > mid) return Query(rc, mid + 1, e, l, r);
return Merge(Query(lc, b, mid, l, r), Query(rc, mid + 1, e, l, r));
}
} segt;
void solve() {
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
bit1.add(i, a[i]);
bit2.add(i, i);
}
for (int i = 1, addcnt = 0; i <= q; ++i) {
scanf("%d", &type[i]);
if (type[i] == 1) {
scanf("%lld", &qv[i]);
line[++tot] = (Line){i, -addcnt, qv[i]};
} else if (type[i] == 2) {
++addcnt;
} else if (type[i] == 3) {
scanf("%d %d", &ql[i], &qr[i]);
}
}
for (int l = 1, r; l <= tot; l = r + 1) {
r = min(tot, l + B - 1);
for (int j = l; j <= r; ++j) {
if (top && stk[top].k == line[j].k) {
if (stk[top].b > line[j].b) {
--top;
} else {
continue;
}
}
while (top > 1 && Check(stk[top - 1], stk[top], line[j])) {
--top;
}
stk[++top] = line[j];
}
for (int i = 1, ptr = 1; i <= n; ++i) {
if (vis[i]) continue;
while (ptr < top && stk[ptr].val(i) >= stk[ptr + 1].val(i)) {
++ptr;
}
if (stk[ptr].val(i) <= a[i]) {
vis[i] = 1;
for (int j = l; j <= r; ++j) {
if (line[j].val(i) <= a[i]) {
//cerr << "wow " << i << ' ' << line[j].id << endl;
ins[line[j].id].push_back(i);
break;
}
}
}
}
}
for (int i = 1, addcnt = 0; i <= q; ++i) {
if (type[i] == 1) {
LL v = qv[i];
int L = 1, R = n, pos = n + 1;
while (L <= R) {
int mid = (L + R) >> 1;
if (segt.Ask(1, 1, n, mid) + 1LL * mid * addcnt >= v) {
pos = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
if (pos <= n) {
segt.Cover(1, 1, n, pos, n, v, addcnt);
}
for (auto j : ins[i]) {
segt.Insert(1, 1, n, j, v, addcnt);
bit1.add(j, -a[j]);
bit2.add(j, -j);
}
} else if (type[i] == 2) {
++addcnt;
} else if (type[i] == 3) {
int l = ql[i], r = qr[i];
LL ans = bit1.qry(l, r);
ans += bit2.qry(l, r) * addcnt;
Node cur = segt.Query(1, 1, n, l, r);
//cerr << cur.vsum << ' ' << cur.isum << ' ' << cur.itsum << endl;
ans += cur.vsum;
ans += cur.isum * addcnt - cur.itsum;
printf("%lld\n", ans);
}
}
}
int main() {
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 22276kb
input:
13 11 6 14 14 6 3 6 4 13 10 3 12 5 11 1 2 2 2 2 1 11 3 4 6 2 1 6 2 1 9 3 2 13
output:
33 107
result:
ok 2 number(s): "33 107"
Test #2:
score: 0
Accepted
time: 1ms
memory: 22836kb
input:
5000 5000 29940 259997 53132 912489 608312 594283 432259 344137 889466 383028 320097 337418 571199 372832 563110 542407 133378 998389 238387 120880 477310 634888 191990 133585 935315 558139 141724 893331 190118 991968 843042 384930 935256 891482 123419 91431 955722 376987 197566 106433 234494 645967...
output:
512185934 455189773 121665669 408693244 291779262 45671866 242375008 302245547 222004631 41963113 343434445 347127029 183849524 2144625 278637672 220461451 20719635 108759503 22099550 34631220 55848925 92362584 36949030 86469096 43509864 50829332 1334865 76069109 114623436 13564322 79974466 15230088...
result:
ok 1671 numbers
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 20820kb
input:
5000 5000 754848159362 799142221874 945332296572 929342054343 220343371940 207059247564 870301066785 609144766745 830351478389 198801101804 768950635554 592202774571 800496073014 730985048260 581401590014 934021096780 587980626010 77068543347 206074783770 390850923112 122794404396 281461236458 11092...
output:
202297713538655 963167738224120 194349368397972 39703523008217 175276724949769 115828286259777 53486037590699 32085609121169 79863137176116 53634397678952 11984901865039 53065256000101 29045072084569 26415198892331 75111789355520 75384800485844 34569350111656 133340053405484 51324651695791 973372919...
result:
wrong answer 1st numbers differ - expected: '116508179221533', found: '202297713538655'