QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#383469#3746. 千万别用树套树visionWA 164ms5152kbC++171.1kb2024-04-09 14:37:282024-04-09 14:37:29

Judging History

This is the latest submission verdict.

  • [2024-04-09 14:37:29]
  • Judged
  • Verdict: WA
  • Time: 164ms
  • Memory: 5152kb
  • [2024-04-09 14:37:28]
  • Submitted

answer

#include <bits/stdc++.h>
#define int long long
#define lson k<<1
#define rson (k<<1)|1
#define debug cout<<666<<endl;
using namespace std;
const int N=1e6+5;
int tr[3][N];//0shi kai shi 1shi jie shu 
// int tr[N];
int n,q;
int lowbit(int x){
	return x&(-x);
}
void add(int w,int x,int op){
	for(int i=w;i<=n;i+=lowbit(i)){
		tr[op][i]+=x;
	}
}
int query(int x,int op){
	int sum=0;
	while(x){
		sum+=tr[op][x];
		x-=lowbit(x);
	}
	// cout<<sum<<":";
	return sum;
}
void vision()
{
	while(cin>>n>>q){
		int sum=0;
		while(q--){
			int op,l,r;
			cin>>op>>l>>r;
			if(op==1){
				add(l,1,0);
				add(r,1,1);
				sum++;
			}
			else {
				if(l==r){
					cout<<sum<<"\n";
				}
				else{
					int ans=query(r,0)-query(l-1,0)+query(r,1)-query(l-1,1);
					// cout<<sum<<":";
					cout<<sum-ans<<"\n";
				}
			}
		}
		for(int i=1;i<=n;i++)tr[0][i]=tr[1][i]=0;
	}
	return ;
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t=1;
	// cin>>t;
	while(t--){
		vision();
	}
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 164ms
memory: 5152kb

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'