QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#117882#6675. DS Team Selection 2willowWA 2ms22836kbC++144.9kb2023-07-02 12:51:132023-07-02 12:51:15

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-02 12:51:15]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:22836kb
  • [2023-07-02 12:51:13]
  • 提交

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'