QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#382707#3746. 千万别用树套树ucup-team1251WA 280ms11608kbC++202.6kb2024-04-08 17:58:282024-04-08 17:58:28

Judging History

This is the latest submission verdict.

  • [2024-04-08 17:58:28]
  • Judged
  • Verdict: WA
  • Time: 280ms
  • Memory: 11608kb
  • [2024-04-08 17:58:28]
  • Submitted

answer

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define buff ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;

class ST
{
public:

	ST(int x = 1000010)
	{
		n = x;
		sza = 0;
		int np = getsize(n);
		sg.assign(np, 0);
		stm.assign(np, 0);
	}

	ST(vector<ll>& aa, int x = -1)
	{
		a = aa;
		if(x == -1)
			n = a.size() - 1;
		else
			n = x;
		sza = a.size();
		int np = getsize(n);
		sg.assign(np, 0);
		stm.assign(np, 0);
		build(1, n);
	}

	void update(int p, ll x)
	{
		_update(p, p, x, 1, n);
	}

	void update(int l, int r, ll x)
	{
		_update(l, r, x, 1, n);
	}

	ll query(int p)
	{
		return _query(p, p, 1, n);
	}

	ll query(int l, int r)
	{
		if(l > r)return 0;
		return _query(l, r, 1, n);
	}

protected:

	void _update(int L, int R, ll x, int l, int r, int p = 1)
	{
		stm[p] += x * (R - L + 1);
		if(L <= l && r <= R)
		{
			sg[p] += x;
			return;
		}
		int mid = (l + r) >> 1;
		if(R <= mid)
			_update(L, R, x, l, mid, p << 1);
		else if(L > mid)
			_update(L, R, x, mid + 1, r, p << 1 | 1);
		else
		{
			_update(L, mid, x, l, mid, p << 1);
			_update(mid + 1, R, x, mid + 1, r, p << 1 | 1);
		}
	}

	ll _query(int L, int R, int l, int r, int p = 1)
	{
		if(L <= l && r <= R)
			return stm[p];
		ll ret = sg[p] * (R - L + 1);
		int mid = (l + r) >> 1;
		if(R <= mid)
			ret += _query(L, R, l, mid, p << 1);
		else if(L > mid)
			ret += _query(L, R, mid + 1, r, p << 1 | 1);
		else
		{
			ret += _query(L, mid, l, mid, p << 1);
			ret += _query(mid + 1, R, mid + 1, r, p << 1 | 1);
		}
		return ret;
	}

private:

	int n;

	int sza;
	vector<ll>a0;
	vector<ll>& a = a0;

	vector<ll>stm, sg;

	unsigned int getsize(unsigned int x)
	{
		unsigned int xx = x;
		xx |= xx >> 1;
		xx |= xx >> 2;
		xx |= xx >> 4;
		xx |= xx >> 8;
		xx |= xx >> 16;
		if(x == ((xx + 1) >> 1))
			return (xx + 1);
		else
			return ((xx + 1) << 1);
	}

	void build(int l, int r, int p = 1)
	{
		if(l == r)
		{
			if(l < sza)
				stm[p] = a[l];
			else
				stm[p] = 0;
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, p << 1);
		build(mid + 1, r, p << 1 | 1);
		stm[p] = stm[p << 1] + stm[p << 1 | 1];
	}

};


int main()
{
	buff;
	int n, q;
	while(cin >> n >> q)
	{
		ST st(n + 10);
		ST st2(n + 10);
		while(q--)
		{
			int op, l, r;
			cin >> op >> l >> r;
			if(op == 1)
			{
				st.update(l, 1);
				st.update(r+1, -1);
				//st2.update(l, -1);
				//st2.update(r+1, 1);
			}
			else if(op == 2)
			{
				cout << st.query(1, r)/* - max(st2.query(1, r),0LL),0LL)*/ << '\n';
			}
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 280ms
memory: 11608kb

input:

100000 100000
1 48500 63742
1 43673 89780
1 6471 44388
1 68054 71541
1 30056 91431
1 49687 70537
2 46899 46900
1 5165 57954
1 85892 88481
2 18060 18062
2 45289 45289
1 18927 67848
1 17389 96139
1 63451 92197
1 15473 87341
1 15162 15744
1 76728 99645
2 48730 48731
2 20886 20888
1 9756 67424
1 23175 4...

output:

2
2
3
7
5
8
9
4
6
2
11
13
13
10
13
15
9
10
14
16
17
16
16
15
2
4
11
6
11
12
23
9
26
3
28
20
12
12
22
30
5
27
6
29
10
14
27
6
17
15
9
30
20
34
7
36
15
8
32
16
21
40
19
2
1
12
12
39
37
13
19
20
1
9
37
1
41
40
20
34
45
43
27
30
47
29
13
50
41
44
29
35
38
53
2
46
54
36
56
58
45
32
42
26
52
42
60
1
4
25
...

result:

wrong answer 511th numbers differ - expected: '123', found: '124'