QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#331388 | #5604. Triangle Containment | ngungu46 | WA | 135ms | 13056kb | C++14 | 2.9kb | 2024-02-18 07:10:36 | 2024-02-18 07:10:36 |
Judging History
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 = 100001;
const double eps = 1e-9;
long long n, x;
vector<pi> c(maxn);
vector<ll> v(maxn);
int sumv[4*maxn+1];
int pos[4*maxn+1];
int split[4*maxn+1];
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;
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7464kb
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: 7588kb
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: 92ms
memory: 12692kb
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: 104ms
memory: 12380kb
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: 100ms
memory: 13056kb
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: 133ms
memory: 12196kb
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: 135ms
memory: 12372kb
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:
-2164034057 -2206573127 2306953703 5187454654 1558842238 4630386581 -202319934 121257014 -3621361546 -3108610227 3253052025 -2478197934 4204564273 1359242153 2531348648 2526515350 -1269547474 5392968762 -2859790166 6380453497 1949643997 -2155001788 1662875274 -537727714 2072303971 -8669067147 380496...
result:
wrong answer 1st lines differ - expected: '15051696338423', found: '-2164034057'