Submission #954320

#	Time	Username	Problem	Language	Result	Execution time	Memory
954320		YassirSalama	Two Currencies (JOI23_currencies)	C++17	0 / 100	5097 ms	38608 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
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
const int MAXN=1e5+100;
const int BQ=316;
inline int64_t gilbertOrder(int x, int y, int pow, int rotate) {
	if (pow == 0) {
		return 0;
	}
	int hpow = 1 << (pow-1);
	int seg = (x < hpow) ? (
		(y < hpow) ? 0 : 3
	) : (
		(y < hpow) ? 1 : 2
	);
	seg = (seg + rotate) & 3;
	const int rotateDelta[4] = {3, 0, 0, 1};
	int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
	int nrot = (rotate + rotateDelta[seg]) & 3;
	int64_t subSquareSize = int64_t(1) << (2*pow - 2);
	int64_t ans = seg * subSquareSize;
	int64_t add = gilbertOrder(nx, ny, pow-1, nrot);
	ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
	return ans;
}
 
struct Query {
	int l, r, id,x,y;
 
	inline pair<int, int> toPair() const {
		return make_pair(l / BQ, ((l / BQ) & 1) ? -r : +r);
	}
};
 
inline bool operator<(const Query &a, const Query &b) {
	return a.toPair() < b.toPair();
}
vector<int> c[MAXN];
vector<Query> queries;
unordered_map<int,int> f,g;
set<int> cc;
int arr[BQ+10];
int arr2[MAXN];
int cnt=0;
int cnt1[BQ+10];
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]]--;
}
vector<pair<int,int>> v[MAXN];
void a(int a,int b){
	int x=-1;
	for(auto y:v[a]){
		if(y.F==b){
			x=y.S;
			break;
		}
	}
	if(x==-1) return;
	for(auto y:c[x]){
		add(y);
	}
}
void re(int a,int b){
	int x=-1;
	for(auto y:v[a]){
		if(y.F==b){
			x=y.S;
			break;
		}
	}
	if(x==-1) return;
	for(auto y:c[x]) remove(y);
}
const int MOD = 1e9 + 7;
const int BUF_SZ = 1 << 15;
inline namespace Input {
char buf[BUF_SZ];
int pos;
int len;
char next_char() {
	if (pos == len) {
		pos = 0;
		len = (int)fread(buf, 1, BUF_SZ, stdin);
		if (!len) { return EOF; }
	}
	return buf[pos++];
}

int read_int() {
	int x;
	char ch;
	int sgn = 1;
	while (!isdigit(ch = next_char())) {
		if (ch == '-') { sgn *= -1; }
	}
	x = ch - '0';
	while (isdigit(ch = next_char())) { x = x * 10 + (ch - '0'); }
	return x * sgn;
}
} 
int ans[MAXN];
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n,m,q;
// cin>>n>>m>>q;
n=read_int();
m=read_int();
q=read_int();
for(int i=1;i<n;i++){
	int a,b;
	a=read_int();
	b=read_int();
	// cin>>a>>b;
	v[a].pb({b,i});
	v[b].pb({a,i});
}
for(int i=0;i<m;i++){
	int t;
	t=read_int();
	// cin>>t;
	int d;
	d=read_int();
	// cin>>d;
	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;
	l=read_int();
	r=read_int();
	x=read_int();
	y=read_int();
	if(l>r) swap(l,r);
	queries.pb({.l=l,.r=r,.id=i,.x=x,.y=y});
}
sort(all(queries));
int l=0;
int r=0;
for(int i=0;i<q;i++){
	int ql=queries[i].l;
	int qr=queries[i].r;
	int id=queries[i].id;
	int x=queries[i].x;
	int y=queries[i].y;
	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=0;
	int k=cnt;
	for(int i=1;i<=BQ;i++){
		if(y>=arr[i]){
			y-=arr[i];
			t=i;
			k-=cnt1[i];
		}else break;
	}
	for(int i=BQ*(t);i<BQ*(t+1);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(x>=k){
		ans[id]=x-k;
	}else ans[id]=-1;
}
for(int i=0;i<q;i++) cout<<ans[i]<<"\n";
}

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