QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#382864#3746. 千万别用树套树ucup-team1251WA 263ms3840kbC++171.5kb2024-04-08 19:52:242024-04-08 19:52:25

Judging History

This is the latest submission verdict.

  • [2024-04-08 19:52:25]
  • Judged
  • Verdict: WA
  • Time: 263ms
  • Memory: 3840kb
  • [2024-04-08 19:52:24]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long	
#define ull unsigned long long
using namespace std;
typedef pair<int,int>PII;
typedef array<int,3>ar;
typedef pair<int,double>PID;
typedef pair<string,string>PSS;
typedef pair<PII,int>PPI;
const ull mask = std::chrono::steady_clock::now().time_since_epoch().count();
const int N=2e5+5;
const int M=1e9+7;
const int base=131;
ull shift(ull x) //树哈希:映射函数 使用ull自然溢出
{
	x ^= mask;
	x ^= x << 13;
	x ^= x >> 7; 
	x ^= x << 17;
	x ^= mask;
	return x;
}
int tr[3][N];
int n;
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int w,int ran)
{
	for(;x<=n;x+=lowbit(x))
	{
		tr[ran][x]+=w;
	}
}
int get(int x,int ran)
{
	int ans=0;
	for(;x>0;x-=lowbit(x))
	{
		ans+=tr[ran][x];
	}
	return ans;
}
int en[N][3];
int st[N][3];
void solve()
{	
	int n,m;
	while(cin>>n>>m)
	{
		int cnt=0;
		for(int i=1;i<=m;i++)
		{
			int op,l,r;
			cin>>op>>l>>r;
			if(op==1)
			{
				cnt++;
				add(l,1,1);
				add(n-r+1,1,2);
				if(r-l+1<=2)
				{
					en[r][r-l+1]++;
					st[l][r-l+1]++;
				}
			}
			else 
			{
				int l1=get(l-1,1);
				int r1=get(r-1,2);
				int ne=cnt-l1-r1;
				for(int i=l;i<=r;i++)
				{
					for(int k=1;k<=2;k++)
					{
						int ll=i-k+1;
						int rr=i+k-1;
						if(ll<l)ne-=en[i][k];
						if(rr>r)ne-=st[i][k];
					}
				}
				cout<<ne<<"\n";
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int k=1;k<=2;k++) en[i][k]=0,st[i][k]=0,tr[i][k]=0;
		}
	}
	
}
signed main()	
{
	ios::sync_with_stdio(0);
	//	cin.tie(0),cout.tie(0);
	int t=1;
	//		cin>>t;
	while(t--)
		solve();	
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 263ms
memory: 3840kb

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:

6
8
8
14
14
16
18
18
20
21
26
26
30
30
31
31
33
34
34
34
35
35
35
35
36
39
40
43
44
44
45
45
46
49
49
50
50
50
51
52
52
52
54
56
56
56
56
56
57
57
57
57
61
63
63
63
63
63
63
63
64
65
65
65
65
65
65
67
68
68
68
68
71
72
72
75
75
75
75
77
77
77
77
79
80
81
81
81
88
88
88
90
90
90
93
96
96
96
96
97
98
...

result:

wrong answer 1st numbers differ - expected: '2', found: '6'