QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127590#5604. Triangle Containmentbatrr#WA 101ms17108kbC++172.8kb2023-07-19 20:06:512023-07-19 20:06:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-19 20:06:55]
  • 评测
  • 测评结果:WA
  • 用时:101ms
  • 内存:17108kb
  • [2023-07-19 20:06:51]
  • 提交

answer

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 300500, inf = 1e9, mod = 998244353;
const ll INF = 1e18;

int sum(int a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

int sub(int a, int b) {
    a -= b;
    if (a < 0)
        a += mod;
    return a;
}

int mult(int a, int b) {
    return 1ll * a * b % mod;
}

int bp(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

int inv(int x) {
    return bp(x, mod - 2);
}
int s, t;
int n;
typedef long double ld;
int x;
struct pt{
    ll x, y;
    pt() {
        x = y = 0;
    }
    pt(ll xx, ll yy) {
        x = xx;
        y = yy;
    }
};
const int maxN = 1e5 + 10;
int id[maxN][2];
pt st;
pt a[maxN];
ll cost[maxN];
bool cmp(pt a, pt b) {
    ll difAx = a.x - st.x;
    ll difAy = a.y - st.y;
    ll difBx = b.x - st.x;
    ll difbY = b.y - st.y;
    return difAx * difbY > difAy * difBx;
}
ll fenw[maxN];
int ans[maxN];
ll get(int x) {
    ll s = 0;
    while (x > 0) {
        s += fenw[x];
        x &= (x - 1);
    }
    return s;
}
void upd(int x, ll by) {
    while (x < maxN) {
        fenw[x] += by;
        x = (x | (x - 1)) + 1;
    }
}
void solve() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        pt t;
        cin >> t.x >> t.y;
        a[i] = t;
        cin >> cost[i];
    }
    map<pair<ll,ll>,int> s;
    for (int i = 1; i <= n; i++) {
        s[{a[i].x, a[i].y}] = i;
    }
    for (int z = 0; z < 2; z++) {
        if (z == 0) {
            st.x = 0;
            st.y = 0;
        }
        else {
            st.x = x;
            st.y = 0;
        }
        vector<pt> T;
        for (int i = 1; i <= n; i++) {
            T.emplace_back(a[i]);
        }
        sort(T.begin(), T.end(), cmp);
        for (int i = 0; i < T.size(); i++) {
            id[s[{T[i].x, T[i].y}]][z] = i;
        }
    }
    vector<int> S(n);
    iota(S.begin(), S.end(), 1);
    sort(S.begin(), S.end(), [&](int x, int y) {
        return id[x][1] > id[y][1];
    });
//    for (int i = 1; i <= n; i++) {
//        cout << id[i][0] << " " << id[i][1] << " ??? " << endl;
//    }
    for (int u : S) {
        ans[u] = get(id[u][0] + 1);
        upd(id[u][0] + 1, cost[u]);
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << '\n';

}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
//        cout << "Case #" << i << endl;
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5524kb

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: 5712kb

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: 96ms
memory: 17108kb

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: 58ms
memory: 16192kb

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: 0
Accepted
time: 54ms
memory: 17012kb

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 #6:

score: 0
Accepted
time: 98ms
memory: 16204kb

input:

99999 1000000000
499994038 499999999 998430190
500036272 499999997 789110725
499988970 499999999 119471973
500042096 499999996 855486238
499953314 499999995 464948333
499979222 499999999 573710457
500002347 499999999 385287206
500030797 499999998 589559003
500043266 499999996 394228619
500028049 499...

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 #7:

score: -100
Wrong Answer
time: 101ms
memory: 16208kb

input:

99999 1000000000
500015023 90276 306948325
499983944 103118 727377493
500025915 268634 390844401
499969478 372636 395763733
500025195 253915 906667281
500002248 2021 592484584
500028251 319247 781019435
500002485 2470 479698120
500019573 153240 55967591
499996332 5381 572934141
500029257 342388 5702...

output:

2130933239
2088394169
-1988013593
892487358
1558842238
335419285
-202319934
121257014
673605750
1186357069
-1041915271
1816769362
-90403023
1359242153
-1763618648
-1768451946
-1269547474
1098001466
1435177130
2085486201
1949643997
2139965508
1662875274
-537727714
2072303971
-79132555
-490000418
1346...

result:

wrong answer 1st lines differ - expected: '15051696338423', found: '2130933239'