| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1161190 | brinton | Two Currencies (JOI23_currencies) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> edges;
#define int long long
struct dataS{
// now is bit
private:
vector<int> tree;
int N;
int query(int idx){
int ans = 0;
for(int i = idx;i >= 1;i -= i&-i){
ans += tree[i];
}
return ans;
}
public:
dataS(int iN){
N = iN;
tree.resize(N+1);
}
void modify(int u,int v,int dv){
// modify v(back)
for(int i = v;i <= N;i += i&-i){
tree[i] += dv;
}
}
int query(int u,int v){
return query(v)-query(u);
}
};
signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
//start here
int N,C,Q;
cin >> N >> C >> Q;
edges.resize(N+1);
vector<array<int,2>> edgeUV;
for(int i = 0;i < N-1;i++){
int a,b;
cin >> a >> b;
edges[a].push_back(b);
edges[b].push_back(a);
edgeUV.push_back({a,b});
}
vector<array<int,3>> checkP;// cost,u,v
for(int i = 0;i < C;i++){
int loc,cost;
cin >> loc >> cost;
loc--;
checkP.push_back({cost,edgeUV[loc][0],edgeUV[loc][1]});
}
vector<array<int,5>> qry;
for(int i = 0;i < Q;i++){
int u,v,g,s;
cin >> u >> v >> g >> s;
qry.push_back({u,v,g,s,i});
}
sort(checkP.begin(),checkP.end());
vector<int> ans(Q);
dataS silver(N+1);
dataS gold(N+1);
dataS change(N+1);
for(auto [cost,a,b]:checkP){
gold.modify(a,b,1);
}
// cout << "input ok" << endl;
auto whole = [&](int l,int r,vector<array<int,5>> cq,auto whole){
if(l == r){
// answer queries;
for(auto [u,v,g,s,idx]:cq){
ans[idx] = max(-1,g-(gold.query(u,v)-change.query(u,v)));
}
return;
}
// put half queries in
int m = (l+r)/2;
for(int i = l;i <= m;i++){
// ! full point change to hld
change.modify(checkP[i][1],checkP[i][2],1);
silver.modify(checkP[i][1],checkP[i][2],checkP[i][0]);
}
vector<array<int,5>> ql,qr;
for(auto [u,v,g,s,idx]:cq){
bool ok = silver.query(u,v) <= s;
if(ok){
qr.push_back({u,v,g,s,idx});
}else{
ql.push_back({u,v,g,s,idx});
}
}
whole(m+1,r,qr,whole);
// remove;
for(int i = l;i <= m;i++){
// ! full point change to hld
change.modify(checkP[i][1],checkP[i][2],-1);
silver.modify(checkP[i][1],checkP[i][2],-checkP[i][0]);
}
whole(l,m,ql,whole);
};
whole(0,C-1,qry,whole);
for(auto i:ans)cout << i << " ";
}
// 整體2分