QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #242159 | #7047. Pot!! | maghrabyJr_# | AC ✓ | 120ms | 19568kb | C++20 | 3.5kb | 2023-11-06 23:48:06 | 2023-11-06 23:48:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
int mx;
};
struct seg_tree{
vector<node> tree;
vector<int> lazy;
int sz = 1;
void init(int n){
while(sz < n) sz *= 2;
tree.resize(2 * sz, {0});
lazy.resize(2 * sz, 0);
}
node single(int v){
return {v};
}
node merge(node &a, node &b){
return {max(a.mx, b.mx)};
}
node neutral(){
return {0};
}
void propagate(int x, int lx, int rx){
if(!lazy[x]) return;
tree[x].mx += lazy[x];
if(lx + 1 != rx){
lazy[2 * x + 1] += lazy[x];
lazy[2 * x + 2] += lazy[x];
}
lazy[x]= 0;
}
void update(int l, int r, int val, int x, int lx, int rx){
propagate(x, lx, rx);
if(l >= rx || lx >= r) return;
if(l <= lx && rx <= r){
lazy[x] += val;
propagate(x, lx, rx);
return;
}
int m = (lx + rx) >> 1;
update(l, r, val, 2 * x + 1, lx, m);
update(l, r, val, 2 * x + 2, m, rx);
tree[x]= merge(tree[2 * x + 1], tree[2 * x + 2]);
}
void update(int l, int r, int v){
update(l, r, v, 0, 0, sz);
}
node query(int l, int r, int x, int lx, int rx){
propagate(x, lx, rx);
if(l >= rx || lx >= r) return neutral();
if(lx >= l && rx <= r){
return tree[x];
}
int m = (lx + rx) >> 1;
node s1 = query(l, r, 2 * x + 1, lx, m);
node s2 = query(l, r, 2 * x + 2, m, rx);
return merge(s1, s2);
}
node query(int l, int r){
return query(l, r, 0, 0, sz);
}
};
int32_t main() {
cin.tie(0);
cout.sync_with_stdio(0);
int n, q;
cin>>n>>q;
vector<int> primes = {2, 3, 5, 7};
vector<seg_tree> st(4);
for(int i = 0; i < 4; i++){
st[i].init(n);
}
while(q--)
{
string qs; cin>>qs;
if(qs == "MULTIPLY"){
int L, R, X;
cin>>L>>R>>X;
for(int i = 0; i < 4; i++)
{
int p = primes[i];
int pw = 0;
while(X % p == 0){
X /= p; pw++;
}
if(pw) st[i].update(L - 1, R, pw);
}
}else{
int L, R;
cin>>L>>R;
int res= 0;
for(int i = 0; i < 4; i++){
res= max(res, st[i].query(L - 1, R).mx);
}
cout<<"ANSWER "<<res<<"\n";
}
}
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
5 6 MULTIPLY 3 5 2 MULTIPLY 2 5 3 MAX 1 5 MULTIPLY 1 4 2 MULTIPLY 2 5 5 MAX 3 5
output:
ANSWER 1 ANSWER 2
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
100 1000 MULTIPLY 3 13 8 MULTIPLY 35 86 9 MAX 5 92 MAX 30 86 MAX 4 99 MAX 36 66 MULTIPLY 27 41 5 MAX 21 40 MULTIPLY 5 20 10 MAX 7 98 MAX 10 10 MAX 40 44 MAX 27 47 MAX 37 54 MAX 61 72 MULTIPLY 10 13 8 MAX 19 30 MAX 27 96 MULTIPLY 54 94 9 MAX 29 88 MAX 7 45 MULTIPLY 21 96 7 MULTIPLY 77 98 9 MULTIPLY 3...
output:
ANSWER 3 ANSWER 2 ANSWER 3 ANSWER 2 ANSWER 2 ANSWER 4 ANSWER 4 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 1 ANSWER 2 ANSWER 4 ANSWER 7 ANSWER 4 ANSWER 6 ANSWER 7 ANSWER 6 ANSWER 1 ANSWER 4 ANSWER 2 ANSWER 8 ANSWER 4 ANSWER 6 ANSWER 11 ANSWER 11 ANSWER 11 ANSWER 7 ANSWER 7 ANSWER 7 ANSWER 7 ANSWER 8 ...
result:
ok 491 lines
Test #3:
score: 0
Accepted
time: 3ms
memory: 3968kb
input:
1000 10000 MULTIPLY 303 613 4 MAX 205 586 MULTIPLY 392 430 10 MAX 299 404 MAX 566 836 MAX 427 741 MAX 240 721 MAX 520 805 MULTIPLY 107 698 10 MULTIPLY 244 610 3 MAX 627 747 MULTIPLY 537 554 9 MULTIPLY 213 772 8 MAX 419 930 MAX 127 696 MAX 554 894 MAX 588 729 MAX 307 845 MAX 496 921 MULTIPLY 77 598 5...
output:
ANSWER 2 ANSWER 3 ANSWER 2 ANSWER 3 ANSWER 3 ANSWER 2 ANSWER 1 ANSWER 7 ANSWER 7 ANSWER 6 ANSWER 6 ANSWER 7 ANSWER 6 ANSWER 7 ANSWER 7 ANSWER 4 ANSWER 7 ANSWER 2 ANSWER 7 ANSWER 7 ANSWER 1 ANSWER 9 ANSWER 9 ANSWER 6 ANSWER 10 ANSWER 9 ANSWER 11 ANSWER 11 ANSWER 10 ANSWER 10 ANSWER 11 ANSWER 12 ANSWE...
result:
ok 4965 lines
Test #4:
score: 0
Accepted
time: 10ms
memory: 5120kb
input:
10000 10000 MULTIPLY 6735 9303 4 MAX 4205 5392 MAX 2299 3986 MAX 2836 4566 MULTIPLY 4427 8240 8 MULTIPLY 520 8805 9 MAX 3010 8107 MAX 4040 4244 MULTIPLY 2537 2627 9 MAX 1772 8461 MULTIPLY 930 4910 10 MULTIPLY 2696 4127 9 MAX 894 8588 MULTIPLY 4845 7307 6 MAX 2598 5921 MULTIPLY 446 6935 4 MAX 8903 90...
output:
ANSWER 0 ANSWER 0 ANSWER 0 ANSWER 5 ANSWER 2 ANSWER 5 ANSWER 5 ANSWER 5 ANSWER 2 ANSWER 8 ANSWER 8 ANSWER 3 ANSWER 8 ANSWER 7 ANSWER 3 ANSWER 10 ANSWER 5 ANSWER 9 ANSWER 11 ANSWER 11 ANSWER 9 ANSWER 14 ANSWER 11 ANSWER 9 ANSWER 15 ANSWER 3 ANSWER 0 ANSWER 12 ANSWER 15 ANSWER 15 ANSWER 11 ANSWER 16 A...
result:
ok 4979 lines
Test #5:
score: 0
Accepted
time: 87ms
memory: 5224kb
input:
10000 100000 MULTIPLY 6735 9303 7 MULTIPLY 5392 9430 10 MULTIPLY 2836 7404 7 MULTIPLY 4427 8240 5 MAX 4698 8805 MULTIPLY 3010 4610 10 MAX 747 2627 MULTIPLY 8461 8554 7 MULTIPLY 930 4910 7 MULTIPLY 2696 4554 7 MAX 4729 4845 MULTIPLY 496 5921 7 MULTIPLY 446 6935 3 MULTIPLY 5694 9059 10 MULTIPLY 2223 2...
output:
ANSWER 2 ANSWER 0 ANSWER 2 ANSWER 4 ANSWER 2 ANSWER 7 ANSWER 3 ANSWER 7 ANSWER 7 ANSWER 6 ANSWER 2 ANSWER 3 ANSWER 6 ANSWER 4 ANSWER 7 ANSWER 6 ANSWER 7 ANSWER 3 ANSWER 7 ANSWER 7 ANSWER 7 ANSWER 7 ANSWER 6 ANSWER 7 ANSWER 7 ANSWER 7 ANSWER 7 ANSWER 8 ANSWER 9 ANSWER 5 ANSWER 3 ANSWER 12 ANSWER 8 AN...
result:
ok 50025 lines
Test #6:
score: 0
Accepted
time: 118ms
memory: 19476kb
input:
100000 100000 MULTIPLY 7720 11613 9 MAX 46735 69303 MAX 4205 34586 MAX 19430 55392 MAX 33986 62299 MAX 32836 67404 MULTIPLY 30613 94566 5 MULTIPLY 1143 40741 4 MAX 38240 94427 MAX 60520 92721 MAX 64698 68805 MAX 18107 43010 MAX 54610 64244 MULTIPLY 20977 34040 6 MAX 747 52627 MULTIPLY 18458 72537 2 ...
output:
ANSWER 0 ANSWER 2 ANSWER 0 ANSWER 0 ANSWER 0 ANSWER 2 ANSWER 1 ANSWER 1 ANSWER 2 ANSWER 1 ANSWER 3 ANSWER 3 ANSWER 2 ANSWER 5 ANSWER 5 ANSWER 5 ANSWER 5 ANSWER 3 ANSWER 13 ANSWER 8 ANSWER 9 ANSWER 13 ANSWER 13 ANSWER 10 ANSWER 15 ANSWER 17 ANSWER 17 ANSWER 6 ANSWER 14 ANSWER 19 ANSWER 12 ANSWER 21 A...
result:
ok 49954 lines
Test #7:
score: 0
Accepted
time: 118ms
memory: 19388kb
input:
100000 100000 MULTIPLY 46735 69303 4 MAX 4205 7720 MAX 19430 21239 MAX 2438 62299 MAX 8856 32836 MAX 11798 40741 MULTIPLY 38240 92721 6 MAX 32286 68805 MAX 10451 18107 MAX 30613 54610 MAX 5854 34040 MULTIPLY 52627 72537 4 MAX 1143 78461 MAX 282 97213 MAX 20538 50930 MULTIPLY 54127 62696 2 MAX 8946 3...
output:
ANSWER 0 ANSWER 0 ANSWER 2 ANSWER 0 ANSWER 0 ANSWER 3 ANSWER 0 ANSWER 3 ANSWER 0 ANSWER 5 ANSWER 5 ANSWER 3 ANSWER 0 ANSWER 0 ANSWER 1 ANSWER 6 ANSWER 7 ANSWER 6 ANSWER 7 ANSWER 7 ANSWER 7 ANSWER 8 ANSWER 3 ANSWER 9 ANSWER 8 ANSWER 12 ANSWER 12 ANSWER 12 ANSWER 11 ANSWER 7 ANSWER 6 ANSWER 9 ANSWER 1...
result:
ok 50061 lines
Test #8:
score: 0
Accepted
time: 119ms
memory: 19412kb
input:
100000 100000 MULTIPLY 39 69303 4 MAX 4205 7720 MAX 19430 21239 MAX 2438 62299 MAX 8856 32836 MAX 11798 40741 MULTIPLY 8366 38240 5 MAX 32286 68805 MAX 10451 18107 MAX 30613 54610 MAX 5854 34040 MULTIPLY 28101 52627 9 MAX 1143 78461 MAX 282 97213 MAX 20538 50930 MULTIPLY 15922 54127 3 MAX 8946 30894...
output:
ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 3 ANSWER 2 ANSWER 7 ANSWER 7 ANSWER 15 ANSWER 15 ANSWER 15 ANSWER 15 ANSWER 15 ANSWER 17 ANSWER 15 ANSWER 18 ANSWER 18 ANSWER 22 ANSWER 22 ANSWER 21 ANSWER 25 ANSWER 25 ANSWER 25 ANSWER...
result:
ok 50061 lines
Test #9:
score: 0
Accepted
time: 106ms
memory: 19568kb
input:
100000 100000 MULTIPLY 39 7720 8 MULTIPLY 2438 21239 7 MULTIPLY 8856 11798 3 MAX 8366 33986 MULTIPLY 10451 32286 9 MAX 30613 94566 MULTIPLY 5854 28101 8 MAX 1143 92721 MAX 282 68805 MAX 18107 20538 MAX 15922 54610 MAX 8946 34040 MULTIPLY 2998 26286 7 MULTIPLY 14681 20977 5 MULTIPLY 21656 31892 7 MUL...
output:
ANSWER 1 ANSWER 2 ANSWER 6 ANSWER 6 ANSWER 3 ANSWER 3 ANSWER 3 ANSWER 6 ANSWER 6 ANSWER 6 ANSWER 6 ANSWER 6 ANSWER 3 ANSWER 6 ANSWER 9 ANSWER 10 ANSWER 10 ANSWER 10 ANSWER 10 ANSWER 10 ANSWER 7 ANSWER 13 ANSWER 16 ANSWER 10 ANSWER 16 ANSWER 13 ANSWER 16 ANSWER 17 ANSWER 17 ANSWER 17 ANSWER 15 ANSWER...
result:
ok 50085 lines
Test #10:
score: 0
Accepted
time: 120ms
memory: 19480kb
input:
100000 100000 MULTIPLY 39 69303 8 MULTIPLY 21239 34586 9 MULTIPLY 8856 55392 9 MAX 33986 62299 MAX 32836 94566 MULTIPLY 8366 94427 4 MAX 60520 92721 MULTIPLY 10451 64698 5 MULTIPLY 5854 43010 4 MAX 34040 64244 MULTIPLY 1143 52627 4 MULTIPLY 20538 38554 2 MULTIPLY 8946 31772 7 MULTIPLY 2998 44910 3 M...
output:
ANSWER 4 ANSWER 4 ANSWER 5 ANSWER 7 ANSWER 10 ANSWER 10 ANSWER 10 ANSWER 15 ANSWER 17 ANSWER 20 ANSWER 20 ANSWER 20 ANSWER 17 ANSWER 2 ANSWER 23 ANSWER 23 ANSWER 2 ANSWER 17 ANSWER 17 ANSWER 23 ANSWER 15 ANSWER 23 ANSWER 10 ANSWER 17 ANSWER 25 ANSWER 26 ANSWER 25 ANSWER 25 ANSWER 26 ANSWER 8 ANSWER ...
result:
ok 50027 lines
Test #11:
score: 0
Accepted
time: 103ms
memory: 19384kb
input:
100000 100000 MULTIPLY 7720 21239 9 MAX 8366 11798 MAX 10451 30613 MAX 1143 28101 MAX 15922 20538 MAX 2998 26286 MULTIPLY 20977 31892 3 MULTIPLY 1324 18458 2 MULTIPLY 9726 32279 9 MULTIPLY 841 18588 7 MAX 12618 23612 MULTIPLY 868 29534 4 MAX 17888 31598 MULTIPLY 12213 31112 2 MULTIPLY 7630 29405 5 M...
output:
ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 5 ANSWER 5 ANSWER 5 ANSWER 3 ANSWER 5 ANSWER 5 ANSWER 6 ANSWER 11 ANSWER 11 ANSWER 9 ANSWER 11 ANSWER 9 ANSWER 12 ANSWER 6 ANSWER 12 ANSWER 12 ANSWER 12 ANSWER 12 ANSWER 5 ANSWER 12 ANSWER 12 ANSWER 12 ANSWER 12 ANSWER 15 ANSWER 15 ANSWER 15 ANSWER...
result:
ok 49817 lines