QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#153708#7047. Pot!!PetroTarnavskyi#WA 2ms3780kbC++232.1kb2023-08-30 19:24:482023-08-30 19:24:49

Judging History

你现在查看的是最新测评结果

  • [2023-08-30 19:24:49]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3780kb
  • [2023-08-30 19:24:48]
  • 提交

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'