QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#825415 | #9774. Same Sum | ucup-team3691# | TL | 1ms | 3688kb | C++14 | 4.5kb | 2024-12-21 19:13:16 | 2024-12-21 19:13:17 |
Judging History
你现在查看的是最新测评结果
- [2025-01-11 11:59:18]
- hack成功,自动添加数据
- (/hack/1443)
- [2024-12-23 17:02:06]
- hack成功,自动添加数据
- (/hack/1310)
- [2024-12-23 16:48:26]
- hack成功,自动添加数据
- (/hack/1309)
- [2024-12-23 16:33:45]
- hack成功,自动添加数据
- (/hack/1308)
- [2024-12-23 16:23:53]
- hack成功,自动添加数据
- (/hack/1307)
- [2024-12-23 16:13:08]
- hack成功,自动添加数据
- (/hack/1306)
- [2024-12-23 15:54:42]
- hack成功,自动添加数据
- (/hack/1305)
- [2024-12-23 14:58:39]
- hack成功,自动添加数据
- (/hack/1304)
- [2024-12-23 09:58:11]
- hack成功,自动添加数据
- (/hack/1302)
- [2024-12-23 09:47:22]
- hack成功,自动添加数据
- (/hack/1301)
- [2024-12-23 09:41:23]
- hack成功,自动添加数据
- (/hack/1300)
- [2024-12-23 09:26:32]
- hack成功,自动添加数据
- (/hack/1299)
- [2024-12-23 09:19:58]
- hack成功,自动添加数据
- (/hack/1298)
- [2024-12-23 09:13:29]
- hack成功,自动添加数据
- (/hack/1297)
- [2024-12-22 18:52:18]
- hack成功,自动添加数据
- (/hack/1296)
- [2024-12-22 18:13:14]
- hack成功,自动添加数据
- (/hack/1294)
- [2024-12-21 19:13:16]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
using ll = long long;
using ull = unsigned long long;
string to_string(const string &s) {
return '"' + s + '"';
}
string to_string(bool b) {
return b ? "true" : "false";
}
template <typename A, typename B>
string to_string(const pair<A, B> &p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename T>
string to_string(const T &v) {
string s = "{";
bool first = true;
for (const auto &it : v) {
if (!first)
s += ", ";
else
first = false;
s += to_string(it);
}
return s += "}";
}
void debug_out() {
cerr << endl;
}
template <typename T, typename... Args>
void debug_out(const T &first, const Args&... rest) {
cerr << to_string(first) << " ";
debug_out(rest...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto startTime = high_resolution_clock::now();
int get_time() {
auto stopTime = chrono::high_resolution_clock::now();
auto duration = duration_cast<milliseconds>(stopTime - startTime);
return duration.count(); // in ms
}
const int DIM = 2e5 + 5;
const int P = 10;
struct sums {
uint64_t s[P + 1];
};
struct node {
int mx, mn;
sums s, sn;
};
int n, k, q;
int a[DIM];
uint64_t c[P + 1][P + 1];
uint64_t lazy[4 * DIM];
node arb[4 * DIM];
void init() {
c[0][0] = 1;
for (int i = 1; i <= P; ++i) {
c[i][0] = 1;
for (int j = 1; j <= i; ++j) {
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
}
void comb(sums &x, sums &y, sums &z) {
for (int i = 0; i <= P; ++i) {
x.s[i] = y.s[i] + z.s[i];
}
}
void comb(node &x, node &y, node &z) {
comb(x.sn, y.sn, z.sn);
comb(x.s, y.s, z.s);
x.mx = max(y.mx, z.mx);
x.mn = min(y.mn, z.mn);
}
void recalc(sums &x, uint64_t v) {
for (int i = P; i >= 1; --i) {
uint64_t val = 1;
for (int j = 1; j <= i; ++j) {
val = val * v;
x.s[i] += c[i][j] * val * x.s[i - j];
}
}
}
void recalc(node &x, int v) {
recalc(x.s, v);
recalc(x.sn, -v);
x.mn += v;
x.mx += v;
}
void propag(int nod) {
if (!lazy[nod]) {
return;
}
for (int i = nod * 2; i <= nod * 2 + 1; ++i) {
lazy[i] += lazy[nod];
recalc(arb[i], lazy[nod]);
}
lazy[nod] = 0;
}
void build(int st = 1, int dr = n, int nod = 1) {
if (st == dr) {
uint64_t x = 1, xn = 1;
for (int i = 1; i <= P; ++i) {
x = x * a[st];
xn = xn * -uint64_t(a[st]);
arb[nod].s.s[i] = x;
arb[nod].sn.s[i] = xn;
}
arb[nod].s.s[0] = arb[nod].sn.s[0] = 1;
arb[nod].mn = arb[nod].mx = a[st];
return;
}
int mij = (st + dr) / 2;
build(st, mij, nod * 2);
build(mij + 1, dr, nod * 2 + 1);
comb(arb[nod], arb[nod * 2], arb[nod * 2 + 1]);
}
void update(int x, int y, int v, int st = 1, int dr = n, int nod = 1) {
if (x <= st && dr <= y) {
lazy[nod] += v;
recalc(arb[nod], v);
return;
}
propag(nod);
int mij = (st + dr) / 2;
if (x <= mij) {
update(x, y, v, st, mij, nod * 2);
}
if (mij + 1 <= y){
update(x, y, v, mij + 1, dr, nod * 2 + 1);
}
comb(arb[nod], arb[nod * 2], arb[nod * 2 + 1]);
}
node query(int x, int y, int st = 1, int dr = n, int nod = 1) {
if (x <= st && dr <= y) {
return arb[nod];
}
propag(nod);
int mij = (st + dr) / 2;
if (x <= mij && mij + 1 <= y) {
node ans;
node l = query(x, y, st, mij, nod * 2);
node r = query(x, y, mij + 1, dr, nod * 2 + 1);
comb(ans, l, r);
return ans;
}
if (x <= mij) {
return query(x, y, st, mij, nod * 2);
}
return query(x, y, mij + 1, dr, nod * 2 + 1);
}
void solve() {
init();
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
build();
for (int i = 1; i <= q; ++i) {
int t, x, y, v;
cin >> t >> x >> y;
if (t == 1) {
cin >> v;
update(x, y, v);
} else {
node g = query(x, y);
update(x, y, -g.mx - g.mn);
node h = query(x, y);
update(x, y, g.mx + g.mn);
bool ok = true;
for (int i = 1; i <= P; ++i) {
if (g.s.s[i] != h.sn.s[i]) {
ok = false;
break;
}
}
cout << (ok ? "YES" : "NO") << "\n";
}
}
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3688kb
input:
8 4 1 2 3 4 5 6 7 8 2 1 8 1 1 4 4 2 1 6 2 1 8
output:
YES NO YES
result:
ok 3 token(s): yes count is 2, no count is 1
Test #2:
score: -100
Time Limit Exceeded
input:
200000 200000 0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 1 ...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...