QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#331385#5604. Triangle Containmentngungu46RE 1ms3620kbC++142.9kb2024-02-18 07:07:122024-02-18 07:07:12

Judging History

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

  • [2024-02-18 07:07:12]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3620kb
  • [2024-02-18 07:07:12]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <sstream>
#include <complex>
#include <ctime>
#include <cassert>
#include <functional>

#define REP(i,s,t) for(i=(s);i<(t);i++);
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<long long, long long> pi;
typedef vector<ll> vl;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<vector<ll> > mat;
typedef priority_queue<ll, vector<ll>, greater<ll> > minpq;
const ll inf = 1ll << 60;
const ll mod = 1e9 + 7;
const long long maxn = 1001;
const double eps = 1e-9;

long long n, x;
vector<pi> c(maxn);
vector<ll> v(maxn);
int sumv[4*maxn];
int pos[4*maxn];
int split[4*maxn];

long long cross(pi a, pi b){
    return (a.first-x) * b.second - a.second * (b.first-x);
}

long long cross2(pi a, pi b){
    return a.first*b.second - a.second*b.first;
}

void build(vector<ll> &id, ll l, ll r, ll k){
    if(l==r){
        pos[k] =  id[l];
        split[k] = id[l];
        return;
    }

    ll mid = (l+r)>>1;
    build(id, l, mid, 2*k+1);
    build(id, mid+1, r, 2*k+2);
    pos[k] = pos[2*k+1];
    split[k] = pos[2*k+2];
}

ll query(ll l, ll r, ll nl, ll nr, ll k){
    if(r < nl || l > nr) return 0;
    if( l <= nl && nr <= r) return sumv[k];
    ll mid = (nl+nr)>>1;
    ll res1 = query(l,r,nl,mid,2*k+1);
    ll res2 = query(l,r,mid+1,nr,2*k+2);
    return res1+res2;
}

void update(ll id, ll l, ll r, ll k){
    if(l==r){
        sumv[k] += v[id];
        return;
    }
    ll mid = (l+r)>>1;
    if(cross(c[id], c[split[k]])<0){
        update(id, l, mid, 2*k+1);
    }
    else{
        update(id, mid+1, r, 2*k+2);
    }

    sumv[k] = sumv[2*k+1] + sumv[2*k+2];
}


int main(){
    cin >> n >> x;
    vector<ll> idx(n);
    vector<ll> idx2(n);
    for(ll i = 0; i < n; i++){
        cin >> c[i].first >> c[i].second >> v[i];
        idx[i] = i;
        idx2[i] = i;
    }

    sort(idx.begin(), idx.end(), [&](ll i, ll j){
        return cross(c[i], c[j]) < 0;
    });
    sort(idx2.begin(), idx2.end(), [&](ll i, ll j){
        return cross2(c[i], c[j]) > 0;
    });
    vector<ll> idx3(n);
    for(int i = 0; i < n; i++){
        idx3[idx[i]] = i;
    }
    vector<ll> res(n);
    build(idx, 0, n-1, 0);
    for(ll i = 0; i < n; i++){
        ll id = idx3[idx2[i]];
        // cout << idx2[i] << " " << c[idx2[i]].first <<  " " << c[idx2[i]].second << " " << id << " " << v[idx2[i]] << endl;
        res[idx2[i]] = query(0, id, 0, n-1, 0);
        // cout << res[idx2[i]] << endl;
        update(idx2[i], 0, n-1, 0);
    }
    for(ll i = 0; i < n; i++){
        cout << res[i] << endl;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3620kb

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

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: -100
Runtime Error

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:


result: