QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#387691#3746. 千万别用树套树wanyurukongTL 0ms0kbC++17836b2024-04-12 18:54:072024-04-12 18:54:08

Judging History

This is the latest submission verdict.

  • [2024-04-12 18:54:08]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2024-04-12 18:54:07]
  • Submitted

answer

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#define low(x) (x&-x)
#define int long long
using namespace std;
const int N = 1e6;
int mod = 1e9 + 7;
int n, m;
int g[3001][3001];
int a[N];
int t[N][10];
void add(int s, int e) {
	for (int i = s; i <= n; i += low(i)) 
		t[i][e] += 1;
}
int ask(int e, int s) {
	int ans = 0;
	for (int i = s; i; i -= low(i)) 
		ans += t[s][e];
	return ans;
}
void init() {
	for (int i = 1; i <= N; i++) t[i][0] = t[i][1] = 0;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	while (~scanf("%lld%lld", &n, &m)) {
		init();
		for (int i = 1; i <= m; i++) {
			int op, l, r;
			cin >> op >> l >> r;
			if (op == 1) {
				add(l,0), add(r, 1);
			}
			else {
				cout << ask(0,l) - ask(1,r-1) << endl;
			}
		}
	}
	return 0;
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

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:

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: