QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#504839#9104. Zayin and ForestyaLen#WA 15ms6312kbC++142.2kb2024-08-04 16:39:142024-08-04 16:39:14

Judging History

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

  • [2024-08-04 16:39:14]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:6312kb
  • [2024-08-04 16:39:14]
  • 提交

answer

#include <bits/stdc++.h> 
using namespace std;
const int N = 1e7 + 10; 
#define int long long
#define all(x) (x).begin(), (x).end()
#define peace ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define bcount(t) __builtin_popcount(t)
#define lowbit(x) (x&(-x))
const int inf = 1e18; 


int tree[N];
int a[N]; 
int n;

void add_dandian(int x,int k)
{
	for(int i=x;i<=n;i+=lowbit(i))
	tree[i]+=k;
}

void add(int pos, int val){ // tree为树状数组
	while(pos <= n) // 不能越界
	{
		tree[pos] += val;
		pos += lowbit(pos);
	}
}

int query1(int x){ // a[1]..a[x]的和
	int ans = 0;
	while (x >= 1){
		ans = ans + tree[x];
		x = x - lowbit(x);
	} 
	return ans;
}

int query(int l, int r){ // 前缀相减
	return query1(r) - query1(l-1);//求的是(l,r)里面的所有数的和
}

int f(int x){
	return x + lowbit(x);
}

void solve(){
	int q;
	cin >> n >> q;
	vector<int> op(q), opa(q), opb(q);
	vector<int> nums;
	for(int i = 0	; i < q; i++){
		cin >> op[i] >> opa[i] >> opb[i];
		if(op[i] == 1){
//			遍历算出所有x的f(x),在离散数组中插入,如果原来有的话就直接加num
			int x = opa[i], v = opb[i];
			for(int j = x; j <= n; j = f(j)){
				nums.push_back(j);
			}
		}
	}
	sort(all(nums));
	nums.erase(unique(all(nums)), nums.end());
//	for(auto it:nums){
//		cout << it << " ";
//	}
//	cout << endl;
	
	int nn = n;
	n = nums.size();
	int ind;
	for(int i=1;i<=n;i++){
		a[i] = 0;
		add(i, 0);
	}
	
//	cout << query(1,8);
	for(int i = 0; i < q; i++){
		if(op[i] == 1){
			int x = opa[i], v = opb[i];
			for(int j = x; j <= n; j = f(j)){
				ind = lower_bound(all(nums),j) - nums.begin() + 1;
//				cerr << ind << " " << v << endl;
				add(ind,v);
//				cerr << query(ind,ind) << endl;
			}
			
		}else{
			 
			int l = opa[i], r = opb[i];
			l = lower_bound(all(nums),l) - nums.begin() + 1;
			r = lower_bound(all(nums),r) - nums.begin() + 1;
//			cerr << l << r;
			cout << query(l, r) << endl;	
		}
	}

//	for(int i = 1; i < 1000; i++){
//		cout << f(i) << endl;
//	}

	
}
 
signed main(){
	peace;
	int T = 1;
//	cin >> T;
	while(T--){
		solve();
	} 
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 15ms
memory: 6312kb

input:

1000000000 20000
2 384578735 526547442
1 64211261 592970906
1 512065247 448267721
1 44993150 127180320
1 880319036 927623947
1 170536687 572121854
1 896600029 804033011
1 666246328 754201635
1 654066651 179982083
2 240989825 984888006
2 372004567 858916479
2 76127818 98606736
1 181794163 902842353
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 2nd lines differ - expected: '43148875202', found: '0'