QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333541#5604. Triangle Containmentjoelgun14#WA 129ms12824kbC++141.6kb2024-02-20 07:06:322024-02-20 07:06:32

Judging History

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

  • [2024-02-20 07:06:32]
  • 评测
  • 测评结果:WA
  • 用时:129ms
  • 内存:12824kb
  • [2024-02-20 07:06:32]
  • 提交

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'