QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#74737 | #5000. Balanced Seesaw Array | XKError# | RE | 0ms | 0kb | C++14 | 3.1kb | 2023-02-03 16:36:55 | 2023-02-03 16:36:57 |
Judging History
answer
#include <bits/stdc++.h>
#define maxn 1000005
//#define ll long long
#define inf 1000000000
#define int long long
using namespace std;
int n, q;
int a[maxn];
int s1[maxn];
int s2[maxn];
int tg1[maxn];
int tg2[maxn];
int bel[maxn];
int bl[maxn];
int br[maxn];
void pushdown(int p) {
if (tg1[p] != inf) {
for (int i = bl[p]; i <= br[p]; i++) a[i] = tg1[p];
tg1[p] = inf;
}
if (tg2[p] != inf) {
for (int i = bl[p]; i <= br[p]; i++) a[i] += tg2[p];
tg2[p] = inf;
}
}
void Swork1(int p, int l, int r, int k) {
pushdown(p);
for (int i = l; i <= r; i++) a[i] = k;
s1[p] = s2[p] = 0;
for (int i = bl[p]; i <= br[p]; i++) s1[i] += a[i];
for (int i = bl[p]; i <= br[p]; i++) s2[i] += 1ll * a[i] * i;
}
void Wwork1(int p, int k) {
tg1[p] = k, tg2[p] = inf;
s1[p] = 1ll * k * (br[p] - bl[p] + 1);
s2[p] = 1ll * k * (br[p] + bl[p]) * (br[p] - bl[p] + 1);
}
void Swork2(int p, int l, int r, int k) {
pushdown(p);
for (int i = l; i <= r; i++) a[i] += k;
s1[p] = s2[p] = 0;
for (int i = bl[p]; i <= br[p]; i++) s1[i] += a[i];
for (int i = bl[p]; i <= br[p]; i++) s2[i] += 1ll * a[i] * i;
}
void Wwork2(int p, int k) {
if (tg2[p] == inf) tg2[p] = k;
else tg2[p] += k;
s1[p] += 1ll * k * (br[p] - bl[p] + 1);
s2[p] += 1ll * k * (br[p] + bl[p]) * (br[p] - bl[p] + 1);
}
pair<int, int> Sqry(int p, int l, int r) {
pushdown(p);
pair<int, int> res = {0, 0};
for (int i = l; i <= r; i++) res.first += a[i], res.second += a[i] * i;
return res;
}
pair<int, int> Wqry(int p) {
return {s1[p], s2[p]};
}
pair<int, int> add(pair<int, int> &a, pair<int, int> b) {
a.first += b.first;
a.second += b.second;
}
signed main() {
scanf("%lld%lld", &n, &q);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
int B = sqrt(n), cnt = 0;
for (int i = 1; i <= n; i += B) {
int l = i, r = min(l + B - 1, n);
bl[++cnt] = l;
br[cnt] = r;
tg1[cnt] = tg2[cnt] = inf;
for (int j = l; j <= r; j++) {
bel[j] = cnt;
s1[cnt] += a[j];
s2[cnt] += 1ll * a[j] * j;
}
}
while (q--) {
int op, l, r, k;
scanf("%lld", &op);
if (op == 1) {
scanf("%lld%lld%lld", &l, &r, &k);
if (bel[l] == bel[r]) Swork2(bel[l], l, r, k);
else {
Swork2(bel[l], l, br[bel[l]], k);
Swork2(bel[r], bl[bel[r]], r, k);
for (int i = bel[l] + 1; i < bel[r]; i++) Wwork2(i, k);
}
}
else if (op == 2) {
scanf("%lld%lld%lld", &l, &r, &k);
if (bel[l] == bel[r]) Swork1(bel[l], l, r, k);
else {
Swork1(bel[l], l, br[bel[l]], k);
Swork1(bel[r], bl[bel[r]], r, k);
for (int i = bel[l] + 1; i < bel[r]; i++) Wwork1(i, k);
}
}
else {
scanf("%lld%lld", &l, &r);
pair<int, int> res;
if (bel[l] == bel[r]) res = Sqry(bel[l], l, r);
else {
add(res, Sqry(bel[l], l, br[bel[l]]));
add(res, Sqry(bel[r], bl[bel[r]], r));
for (int i = bel[l] + 1; i < bel[r]; i++) add(res, Wqry(i));
}
if (res.first == 0) {
if (res.second == 0) puts("Yes");
else puts("No");
}
else if (res.second % res.first) puts("No");
else puts("Yes");
}
}
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
3 6 1 2 3 3 1 1 3 1 3 1 1 1 2 3 1 3 2 2 2 0 3 2 3