QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#731434#5604. Triangle Containmentbeamishboys#WA 82ms9428kbC++231.4kb2024-11-10 04:01:342024-11-10 04:01:34

Judging History

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

  • [2024-11-10 04:01:34]
  • 评测
  • 测评结果:WA
  • 用时:82ms
  • 内存:9428kb
  • [2024-11-10 04:01:34]
  • 提交

answer

#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <algorithm>

using namespace std;

int n, x0;
vector<array<int, 3>> spots;

vector<pair<double, int>> ldegs, rdegs;

struct BIT {
	int n;
	vector<long long> bit;

	BIT(int n) : n(n) {
		bit.assign(n, 0);
	}

	void update_bit(int i, long long v) {
		int diff = v - bit[i];
		for(int j=i; j<n; j+=(j&-j)) bit[j] += diff;
	}

	long long query_bit(int i) {
		long long res = 0;
		for(int j=i; j>0; j-=(j&-j)) res += bit[j];
		return res;
	}
};

int main() {
	cin >> n >> x0;
	spots.resize(n);
	for(auto &[x,y,v] : spots) cin >> x >> y >> v;

	ldegs.clear(), rdegs.clear();
	for(int i=0; i<n; ++i) {
		auto [x,y,v] = spots[i];

		double ldeg = atan2(double(y), double(x));
		double rdeg = atan2(double(y), double(x0-x)); // interior angle

		ldegs.push_back({ldeg, i});
		rdegs.push_back({rdeg, i});
	}

	// we will compress the right to be used in a bit
	sort(rdegs.begin(), rdegs.end());
	for(int i=0; i<n; ++i) {
		auto &[v, j] = rdegs[i];
		v = i+1;
		spots[j][1] = v;
	}
	BIT bit(rdegs.size()+10);

	vector<long long> res(n, -1);
	long long curv = 0;
	sort(ldegs.begin(), ldegs.end());

	for(auto [ld, i] : ldegs) {
		res[i] = bit.query_bit(spots[i][1]);
		bit.update_bit(spots[i][1], spots[i][2]);
	}

	for(auto v : res) cout << v << '\n';

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3932kb

input:

5 8
-8 1 1
-1 10 2
0 3 4
7 1 8
8 2 16

output:

0
12
0
0
8

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 4112kb

input:

6 6
0 1 1
2 3 10
2 5 100
3 1 1000
3 5 10000
4 5 100000

output:

0
1000
1010
0
1010
1000

result:

ok 6 lines

Test #3:

score: 0
Accepted
time: 66ms
memory: 9428kb

input:

99999 1000000000
500002962 1 1
500025469 1 1
500044229 1 1
500026049 1 1
499983663 1 1
499965983 1 1
499988191 1 1
499987116 1 1
500029240 1 1
499975570 1 1
499973295 1 1
499986404 1 1
500023312 1 1
499964976 1 1
499952153 1 1
500046927 1 1
499951857 1 1
499984523 1 1
500038724 1 1
499991318 1 1
500...

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:

ok 99999 lines

Test #4:

score: 0
Accepted
time: 82ms
memory: 9408kb

input:

100000 1000000000
-50000 1000000000 454290650
-49999 1000000000 208284433
-49998 1000000000 854275069
-49997 1000000000 627720731
-49996 1000000000 79147837
-49995 1000000000 614585061
-49994 1000000000 438660998
-49993 1000000000 300657551
-49992 1000000000 546865509
-49991 1000000000 353401129
-49...

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:

ok 100000 lines

Test #5:

score: -100
Wrong Answer
time: 77ms
memory: 9312kb

input:

100000 1000000000
-1000000000 1 423302241
-999999999 1 941931570
-999999998 1 801255926
-999999997 1 434775469
-999999996 1 784636342
-999999995 1 41794758
-999999994 1 768189347
-999999993 1 746924545
-999999992 1 259101843
-999999991 1 798620683
-999999990 1 447243634
-999999989 1 848852324
-99999...

output:

0
423302241
941931570
1743187496
434775469
1219411811
476570227
1244759574
746924545
1006026388
1545545228
1992788862
1595776869
1741301021
1964300085
2366293419
714439107
1264446583
1613461411
1685494458
1614464926
2287502754
2500260551
3280639698
1247954584
1730231337
1485698742
2386390413
1671420...

result:

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