QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #701142 | #7047. Pot!! | Loxilante# | RE | 112ms | 17928kb | C++20 | 2.6kb | 2024-11-02 13:49:22 | 2024-11-02 13:49:22 |
Judging History
answer
#define F_C
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i < r; i++)
#define hrp(i, l, r) for(int i = l; i <= r; i++)
#define rev(i, r, l) for(int i = r; i >= l; i--)
#define int ll
using namespace std;
typedef long long ll;
template<typename tn = int> tn next(void) { tn k; cin>>k; return k; }
#ifndef LOCAL
#define D(...) 0
#endif
const int U = 2e5;
const vector<int> P{2, 3, 5, 7};
struct SegTree
{
struct Seg
{
int l, r, maxx, tag;
} seg[U];
void build(int e, int l, int r)
{
seg[e].l = l; seg[e].r = r;
if (l == r) { seg[e].maxx = seg[e].tag = 0; return; }
int mid = l+r>>1;
build(e*2, l, mid);
build(e*2+1, mid+1, r);
}
void spread(int e)
{
if (seg[e].tag)
{
seg[e*2].tag += seg[e].tag;
seg[e*2+1].tag += seg[e].tag;
seg[e*2].maxx += seg[e].tag;
seg[e*2+1].maxx += seg[e].tag;
seg[e].tag = 0;
}
}
void change(int e, int l, int r, int v)
{
if (l <= seg[e].l && seg[e].r <= r) { seg[e].maxx += v; seg[e].tag += v; return; }
spread(e);
int mid = seg[e].l+seg[e].r>>1;
if (l <= mid) change(e*2, l, r, v);
if (r > mid) change(e*2+1, l, r, v);
seg[e].maxx = max(seg[e*2].maxx, seg[e*2+1].maxx);
}
int query(int e, int l, int r)
{
if (l <= seg[e].l && seg[e].r <= r) return seg[e].maxx;
spread(e);
int mid = seg[e].l+seg[e].r>>1, ans = 0;
if (l <= mid) ans = max(ans, query(e*2, l, r));
if (r > mid) ans = max(ans, query(e*2+1, l, r));
return ans;
}
} seg[10];
signed main(void)
{
#ifdef LOCAL
// freopen("C:\\Users\\Loxil\\Desktop\\IN.txt", "r", stdin);
// freopen("C:\\Users\\Loxil\\Desktop\\OUT.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin>>n>>q;
for(auto p: P) seg[p].build(1, 1, n);
while(q--)
{
string ope; int l, r;
cin>>ope>>l>>r;
if (ope == "MULTIPLY")
{
int v = next();
for(auto p: P)
{
int cnt = 0;
while(v%p == 0) cnt++, v /= p;
seg[p].change(1, l, r, cnt);
}
}
else
{
int maxx = 0;
for(auto p: P) maxx = max(maxx, seg[p].query(1, l, r));
cout<<"ANSWER "<<maxx<<endl;
}
}
return 0;
}
/*
5 6
MULTIPLY 3 5 2
MULTIPLY 2 5 3
MAX 1 5
MULTIPLY 1 4 2
MULTIPLY 2 5 5
MAX 3 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11736kb
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: 3ms
memory: 12012kb
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: 15ms
memory: 12088kb
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: 14ms
memory: 11792kb
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: 112ms
memory: 17928kb
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: -100
Runtime Error
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