QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#331385 | #5604. Triangle Containment | ngungu46 | RE | 1ms | 3620kb | C++14 | 2.9kb | 2024-02-18 07:07:12 | 2024-02-18 07:07:12 |
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 = 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...