QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#825150 | #9774. Same Sum | ucup-team045# | TL | 0ms | 3584kb | C++20 | 4.7kb | 2024-12-21 17:31:17 | 2024-12-21 17:31:22 |
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 17:31:17]
- 提交
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<array>
#include<stdint.h>
using namespace std;
using LL = long long;
const int M = 5;
long double C[M + 1][M + 1];
#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
#include<functional>
using namespace std;
struct Info{
array<long double, M + 1> hsh;
Info(array<long double, M + 1> hsh = {}) : hsh(hsh) {}
};
using Tag = long double;
Info operator+(const Info &a, const Info &b){
Info ret;
for(int i = 0; i <= M; i++){
ret.hsh[i] = a.hsh[i] + b.hsh[i];
}
return ret;
}
long double pows[M + 1];
void apply(Info &x, Tag &a, Tag f){
pows[0] = 1;
for(int i = 1; i <= M; i++) pows[i] = pows[i - 1] * f;
for(int i = M; i >= 0; i--){
for(int j = 0; j < i; j++){
x.hsh[i] += C[i][j] * x.hsh[j] * pows[i - j];
}
}
a += f;
}
template<class Info, class Tag>
struct LazySegmentTree{
int n;
vector<Info> info;
vector<Tag> tag;
LazySegmentTree() {}
LazySegmentTree(int n, Info _init = Info()){
init(vector<Info>(n, _init));
}
LazySegmentTree(const vector<Info> &_init){
init(_init);
}
void init(const vector<Info> &_init){
n = (int)_init.size();
info.assign((n << 2) + 1, Info());
tag.assign((n << 2) + 1, Tag());
function<void(int, int, int)> build = [&](int p, int l, int r){
if (l == r){
info[p] = _init[l - 1];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m + 1, r);
pull(p);
};
build(1, 1, n);
}
void pull(int p){
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v){
::apply(info[p], tag[p], v);
}
void push(int p){
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, const Info &v){
if (l == r){
info[p] = v;
return;
}
int m = (l + r) / 2;
push(p);
if (x <= m){
modify(2 * p, l, m, x, v);
}
else{
modify(2 * p + 1, m + 1, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v){
modify(1, 1, n, p, v);
}
Info query(int p, int l, int r, int x, int y){
if (l > y || r < x){
return Info();
}
if (l >= x && r <= y){
return info[p];
}
int m = (l + r) / 2;
push(p);
return query(2 * p, l, m, x, y) + query(2 * p + 1, m + 1, r, x, y);
}
Info query(int l, int r){
return query(1, 1, n, l, r);
}
void modify(int p, int l, int r, int x, int y, const Tag &v){
if (l > y || r < x){
return;
}
if (l >= x && r <= y){
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p);
modify(2 * p, l, m, x, y, v);
modify(2 * p + 1, m + 1, r, x, y, v);
pull(p);
}
void modify(int l, int r, const Tag &v){
return modify(1, 1, n, l, r, v);
}
};
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
for(int i = 0; i <= M; i++){
for(int j = 0; j <= i; j++){
if (!j) C[i][j] = 1;
else C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
int n, q;
cin >> n >> q;
vector<Info> init(n);
for(int i = 0; i < n; i++){
int x;
cin >> x;
init[i].hsh[0] = 1;
for(int j = 1; j <= M; j++){
init[i].hsh[j] = init[i].hsh[j - 1] * x;
}
}
LazySegmentTree<Info, Tag> seg(init);
while(q--){
int op;
cin >> op;
if (op == 1){
int l, r, v;
cin >> l >> r >> v;
seg.modify(l, r, v);
}
else{
int l, r;
cin >> l >> r;
long double ave = seg.query(l, r).hsh[1] / (r - l + 1);
seg.modify(l, r, 0 - ave);
auto hsh = seg.query(l, r).hsh;
bool ok = true;
for(int i = 1; i <= M; i += 2){
if (abs(hsh[i]) > 1e-8){
ok = false;
break;
}
}
cout << (ok ? "YES" : "NO") << '\n';
seg.modify(l, r, ave);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
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 ...