QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333541 | #5604. Triangle Containment | joelgun14# | WA | 129ms | 12824kb | C++14 | 1.6kb | 2024-02-20 07:06:32 | 2024-02-20 07:06:32 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ll long long
using namespace std;
const int lim = 1e5 + 5;
struct fenwick {
int a[lim];
fenwick() {
memset(a, 0, sizeof(a));
}
void upd(int idx, int val) {
++idx;
while(idx < lim) {
a[idx] += val;
idx += idx&-idx;
}
}
ll query(int idx) {
++idx;
ll ret = 0;
while(idx) {
ret += a[idx];
idx -= idx&-idx;
}
return ret;
}
ll query(int l, int r) {
return query(r) - (l == 0 ? 0 : query(l - 1));
}
};
pair<int, int> pvt, l, r;
struct point {
int x, y, pos, treasure;
};
double compute(point x) {
x.x -= pvt.fi;
x.y -= pvt.se;
return x.x / (double)x.y;
}
bool cs(point x, point y) {
return compute(x) < compute(y);
}
int main() {
int n, buang;
cin >> n >> buang;
l = mp(0, 0), r = mp(buang, 0);
point a[n];
pair<int, int> ori[n];
for(int i = 0; i < n; ++i) {
int x, y, v;
cin >> a[i].x >> a[i].y >> a[i].treasure;
ori[i].fi = a[i].x;
ori[i].se = a[i].y;
}
sort(a, a + n, cs);
for(int i = 0; i < n; ++i) {
a[i].pos = i;
}
pvt = r;
sort(a, a + n, cs);
map<pair<int, int>, ll> ans;
fenwick bit;
for(auto x : a) {
ans[mp(x.x, x.y)] = bit.query(x.pos, n);
bit.upd(x.pos, x.treasure);
}
for(auto i : ori) {
cout << ans[i] << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3996kb
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: 1ms
memory: 3932kb
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: 129ms
memory: 12824kb
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: -100
Wrong Answer
time: 122ms
memory: 12468kb
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 -4294967296 -4294967296 -4294967296 0 0 0 0 0 0 -4294967296 -4294967296 0 0 0 0 4294967296 4294967296 0 0 0 0 0 0 0 0 0 -4294967296 0 0 0 0 0 0 0 0 4294967296 4294967296 4294967296 4294967296 0 0 0 0 4294967296 4294967296 4294967296 4294967296 0 0 0 0 4294967296 4294967296 4294967296 42949...
result:
wrong answer 6th lines differ - expected: '0', found: '-4294967296'