Submission #970908

#	Time	Username	Problem	Language	Result	Execution time	Memory
970908		happy_node	Two Currencies (JOI23_currencies)	C++17	30 / 100	289 ms	26872 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=1e5+5;

int N,M,Q;

vector<int> qry[MX];

ll S[MX], T[MX], X[MX], Y[MX], ans[MX];

int L[MX], R[MX];

struct fenwick {
	ll t[MX];

	void upd(int p, ll v) {
		for(int i=p;i<=N;i+=i&-i) t[i]+=v;
	}

	ll que(int p) {
		ll res=0;
		for(int i=p;i>0;i-=i&-i) res+=t[i];
		return res;
	}

	ll que(int l, int r) {
		return que(r)-que(l-1);
	}

	void reset() {
		for(int i=0;i<MX;i++) t[i]=0;
	}
} ft, tt;

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N>>M>>Q;

	for(int i=0;i<N-1;i++) {
		int u,v;
		cin>>u>>v;
	}

	vector<pair<int,int>> e;
	e.push_back({0,0});

	for(int i=0;i<M;i++) {
		int p,c;
		cin>>p>>c;
		e.push_back({c,p});
	}

	sort(e.begin(),e.end());

	for(int i=0;i<Q;i++) {
		cin>>S[i]>>T[i]>>X[i]>>Y[i];
		if(S[i]>T[i]) swap(S[i],T[i]);
		L[i]=0,R[i]=M;
		int m=(L[i]+R[i])/2;
		qry[m].push_back(i);
	}

	for(int ii=0;ii<20;ii++) {
		ft.reset();
		tt.reset();
		// activate

		for(int i=1;i<=M;i++) {
			auto [c,p]=e[i];
			ft.upd(p,1);
		}

		vector<pair<int,int>> nxt;

		for(int i=0;i<=M;i++) {
			auto [c,p]=e[i];
			if(i>0) {
				ft.upd(p,-1);
				tt.upd(p,c);
			}

			for(auto id:qry[i]) {
				ll s=tt.que(S[id],T[id]-1);
				if(s<=Y[id]) {
					ans[id]=ft.que(S[id],T[id]-1);
					L[id]=i+1;
					if(L[id]<=R[id])
						nxt.push_back({(L[id]+R[id])/2, id});
				} else {
					R[id]=i-1;
					if(L[id]<=R[id])
						nxt.push_back({(L[id]+R[id])/2, id});
				}
			}
		}

		for(int i=0;i<=M;i++) qry[i].clear();
		for(auto [i,id]:nxt) qry[i].push_back(id);
	}
	
	for(int i=0;i<Q;i++) {
		if(ans[i]>X[i]) {
			cout<<-1<<'\n';
		} else {
			cout<<X[i]-ans[i]<<'\n';
		}
	}

}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 30 / 30
• Subtask 4: 0 / 32