QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#153708 | #7047. Pot!! | PetroTarnavskyi# | WA | 2ms | 3780kb | C++23 | 2.1kb | 2023-08-30 19:24:48 | 2023-08-30 19:24:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FILL(a, b) memset(a, b, sizeof(a))
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
struct Segtree
{
int n;
vector<PII> t;
void init(int _n)
{
n = 1;
while (n < _n) n *= 2;
t.assign(2 * n, {0, 0});
}
void push(int x)
{
int ps = t[x].S;
t[x].F += ps;
t[x].S = 0;
if (x * 2 >= n)
return;
t[x * 2].S += ps;
t[x * 2 + 1].S += ps;
}
void upd(int v, int tl, int tr, int l, int r, int x)
{
push(v);
if (l <= tl && tr <= r)
{
t[v].S += x;
push(v);
return;
}
if (l >= tr || tl >= r)
return;
int tm = (tl + tr) / 2;
upd(v * 2, tl, tm, l, r, x);
upd(v * 2 + 1, tm, tr, l, r, x);
t[v].F = max(t[v * 2].F, t[v * 2 + 1].F);
}
void upd(int l, int r, int x)
{
upd(1, 0, n, l, r, x);
}
int query(int v, int tl, int tr, int l, int r)
{
push(v);
if (l <= tl && tr <= r)
return t[v].F;
if (l >= tr || tl >= r)
return 0;
int tm = (tl + tr) / 2;
return max(query(v * 2, tl, tm, l, r), query(v * 2 + 1, tm, tr, l, r));
}
int query(int l, int r)
{
return query(1, 0, n, l, r);
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
VI p = {2, 3, 5, 7};
vector<Segtree> st(4);
int n, q;
cin >> n >> q;
FOR (i, 0, 4) st[i].init(n);
FOR (i, 0, q)
{
string s;
cin >> s;
if (s == "MULTIPLY")
{
int l, r, x;
cin >> l >> r >> x;
l--, r--;
FOR (j, 0, 4)
{
int cnt = 0;
while (x % p[j] == 0)
{
cnt++;
x /= p[j];
}
st[j].upd(l, r + 1, cnt);
}
}
else
{
int l, r;
cin >> l >> r;
l--, r--;
int ans = 0;
FOR (j, 0, 4)
{
ans = max(ans, st[j].query(l, r + 1));
}
cout << "ANSWER " << ans << '\n';
}
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3512kb
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: -100
Wrong Answer
time: 2ms
memory: 3780kb
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 0 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 7 ANSWER 3 ANSWER 6 ANSWER 11 ANSWER 11 ANSWER 10 ANSWER 7 ANSWER 7 ANSWER 7 ANSWER 7 ANSWER 8 ...
result:
wrong answer 7th lines differ - expected: 'ANSWER 4', found: 'ANSWER 0'