Submission #954300

#	Time	Username	Problem	Language	Result	Execution time	Memory
954300		YassirSalama	Two Currencies (JOI23_currencies)	C++17	0 / 100	79 ms	7284 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
#ifdef IOI
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=2e5+100;
const int BQ=316;
struct Query{
	int l,r,x,y,id;
	bool operator < (const Query& other){
		if(l/BQ==other.l/BQ)
			return r/BQ<other.r/BQ;
		else return l/BQ<other.l/BQ;
	}
};
vector<int> c[MAXN];
vector<Query> queries;
unordered_map<int,int> f,g;
set<int> cc;
map<pair<int,int>,int> mp;
int arr[BQ+100];
int arr2[MAXN];
int cnt=0;
int cnt1[BQ+100];
void add(int x){
	cnt++;
	arr[f[x]/BQ+1]+=x;
	cnt1[f[x]/BQ+1]++;
	arr2[f[x]]++;
}
void remove(int x){
	cnt--;
	arr[f[x]/BQ+1]-=x;
	cnt1[f[x]/BQ+1]--;
    arr2[f[x]]--;
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<n;i++){
	int a,b;
	cin>>a>>b;
	mp[{a,b}]=mp[{b,a}]=i;
}
for(int i=0;i<m;i++){
	int t;
	cin>>t;
	int d;
	cin>>d;
	// t--;
	cc.insert(d);
	c[t].pb(d);
}
int comp=1;
for(auto x:cc){
	f[x]=comp;
	g[comp]=x;
	comp++;
}
for(int i=0;i<q;i++){
	int l,r,x,y;
	cin>>l>>r>>x>>y;
	if(l>r) swap(l,r);
	// l--,r--;
	queries.pb({l,r,x,y,i});
}
sort(all(queries));
int l=0;
int r=0;
auto a = [&](int a,int b){
	if(!mp.count({a,b}))
		return;
	int x=mp[{a,b}];
	for(auto y:c[x]){
		add(y);
	}
};
auto re = [&](int a,int b){
	if(!mp.count({a,b})) return;
	int x=mp[{a,b}];
	for(auto y:c[x]) remove(y);
};
int ans[q];
for(int i=0;i<q;i++){
	auto [ql,qr,x,y,id]=queries[i];
	while(r<qr){
		a(r,r+1);
		r++;
	}
	while(l>ql){
		a(l,l-1);
		l--;
	}
	while(l<ql){
		re(l,l+1);
		l++;
	}
	while(r>qr){
		re(r,r-1);
		r--;
	}
	int t=1;
	int k=cnt;
	for(int i=1;i<=BQ;i++){
		if(y>=arr[i]&&arr[i]!=0){
			y-=arr[i];
			t++;
			k-=cnt1[i];
		}else break;
	}
	for(int i=BQ*(t-1);i<BQ*(t);i++){
		if(!g.count(i)) continue;
		int c=arr2[i];
		int x=g[i];
		k-=min((y/x),c);
		y-=min(y/x,c)*x;

		// if(y>=arr2[i]*g[i]){
		// 	y-=arr2[i]*g[i];
		// 	k-=arr2[i];
		// }else{
		// 	if(y==0) break;
		// 	int c=arr2[i];
		// 	int x=g[i];
		// 	y/=x;
		// 	k-=min(y,c);
		// 	break;
		// }
	}
	if(x>=k){
		ans[id]=x-k;
	}else ans[id]=-1;
}
for(int i=0;i<q;i++) cout<<ans[i]<<endl;
}

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