Submission #212259

#	Time	Username	Problem	Language	Result	Execution time	Memory
212259		zscoder	Harvest (JOI20_harvest)	C++17	100 / 100	4006 ms	405008 KiB

harvest

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds2;

vi people;
vi apple;
int timer=0;

int to[222222];
ll w[222222];
vector<ll> apples[222222];

int n,m; ll L,C;

ll D(ll x, ll y)
{
	if(x<=y) return y-x;
	return L-(x-y);
}

vector<vi> cycles;
int visited[222222];
int iscyc[222222];
set<int> path;
void getcycles(int u)
{
	//cerr<<u<<' '<<visited[u]<<'\n';
	if(visited[u]==2)
	{
		iscyc[u]=1; cycles.back().pb(u);
	}
	path.insert(u);
	if(visited[to[u]]>0&&path.find(to[u])==path.end())
	{
		visited[u]=1; return ;
	}
	if(visited[to[u]]==2) return ;
	if(visited[to[u]]==1)
	{
		if(visited[u]==1) cycles.pb({});
		visited[to[u]]=2;
		getcycles(to[u]);
		return ;
	}
	//unvisited
	visited[to[u]]=1;
	getcycles(to[u]);
}

vi T[222222]; //tree edges
pbds* A[222222]; //debug 
ll shift[222222];
ll ans[222222];
vi adj[222222];
int subsize[222222];

void dfs(int u, int p=-1)
{
	subsize[u]=1;
	for(int v:adj[u])
	{
		if(iscyc[v]) continue;
		if(v==p) continue;
		T[u].pb(v);
		dfs(v,u);
		subsize[u]+=subsize[v];
	}
}
vector<pair<ll,int> > queries[222222];

void getA(int u, int p=-1)
{
	//for(ll x:apples[u]) A[u].insert({x,++timer}); //later change to dsu on tree
	if(T[u].empty())
	{
		A[u] = new pbds;
	}
	for(int v:T[u])
	{
		getA(v,u);
		if(v==T[u][0])
		{
			A[u]=A[v];
			shift[u]=shift[v]+w[v];
		}
		else
		{
			while(!A[v]->empty())
			{
				ii x = *(A[v]->begin());
				A[v]->erase(A[v]->begin());
				A[u]->insert({x.fi+shift[v]+w[v]-shift[u],x.se});
			}
		}
	}
	for(ll x:apples[u]) A[u]->insert({x-shift[u],++timer});
	if(iscyc[u]) return ;
	for(ii x:queries[u])
	{
		int z = x.se; ll t = x.fi;
		//cerr<<"HERE "<<z<<' '<<A[u]->order_of_key({t+1-shift[u],-1})<<'\n';
		ans[z] = A[u]->order_of_key({t+1-shift[u],-1}); 
	}
}

ll flr(ll a, ll b)
{
	if(a>=0) return a/b;
	else return -((abs(a)+b-1)/b);
}

ll md(ll a, ll b)
{
	a%=b;
	if(a<0) a+=b;
	return a;
}

ll ans2[222222];
struct Fenwick
{
	vector<ll> t;
    Fenwick(int n)
    {
        t.assign(n+1,0);
    }
    void reset(int n)
    {
		t.assign(n+1, 0);
	}
    void update(int p, ll v)
    {
        for (; p < (int)t.size(); p += (p&(-p))) t[p] += v;
    }
    ll query(int r) //finds [1, r] sum
    {                     
        ll sum = 0;
        for (; r; r -= (r&(-r))) sum += t[r];
        return sum;
    }
    ll query(int l, int r) //finds [l, r] sum
    {
		if(l == 0) return query(r);
		return query(r) - query(l-1);
	}
};
pbds2 st[810111];
vi affected;
int mx[810111];
void update(int id, int l, int r, int pos, int v)
{
	if(pos>=r||pos<l) return ;
	if(v>mx[id]) mx[id]=v;
	affected.pb(id);
	st[id].insert(v);
	if(r-l<2) return ;
	int mid=(l+r)>>1;
	update(id*2,l,mid,pos,v); update(id*2+1,mid,r,pos,v);
}

int query(int id, int l, int r, int ql, int qr, int v) //# of elements >= v
{
	if(ql>=r||l>=qr) return 0;
	if(v>mx[id]) return 0;
	if(ql<=l&&r<=qr) return st[id].size()-st[id].order_of_key(v);
	int mid=(l+r)>>1;
	return query(id*2,l,mid,ql,qr,v)+query(id*2+1,mid,r,ql,qr,v);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	const bool DEBUG=0;
	srand(12345);
	for(int cc=1;;cc++)
	{
		n=m=L=C=0;
		if(!DEBUG) cin>>n>>m>>L>>C;
		people.clear(); apple.clear();
		if(DEBUG)
		{
			while(n==0)
			{
				people.clear(); apple.clear();
				L=20;
				int l1 = rand()%1000;
				int l2 = rand()%1000;
				if(l1>l2) swap(l1,l2);
				for(int i=0;i<10;i++)
				{
					int p = rand()%1000;
					if(p<=l1) people.pb(i);
					else if(p<=l2) apple.pb(i);
				}
				n=people.size(); m=apple.size();
				C=rand()%10+1;
			}
		}
		if(!DEBUG)
		{
			for(int i=0;i<n;i++)
			{
				ll x; cin>>x;
				people.pb(x);
			}
			for(int i=0;i<m;i++)
			{
				ll x; cin>>x;
				apple.pb(x);
			}
		}
		//build the graph
		cycles.clear();
		for(int i=0;i<n;i++)
		{
			adj[i].clear();T[i].clear();w[i]=0;to[i]=0;visited[i]=0;iscyc[i]=0;
			shift[i]=0;
			subsize[i]=0;
			apples[i].clear();
			queries[i].clear();
			A[i]=NULL;
		}
		for(int i=0;i<n;i++)
		{
			ll curx = people[i];
			curx-=C;
			curx%=L;
			if(curx<0) curx+=L;
			//first person that is <= curx gets it
			int ub = upper_bound(people.begin(),people.end(),curx)-people.begin();
			ub--;
			if(ub<0)
			{
				ub=int(people.size())-1;
			}
			//ub is the person you want
			//compute the length now
			ll dist = 0;
			if(ub<=i) dist = people[i]-people[ub];
			else dist = L-(people[ub]-people[i]);
			//we want dist >= C
			if(dist<C)
			{
				ll diff = C-dist;
				dist+=((diff+L-1)/L)*L; //ceil(diff/L)*L
			}
			w[i]=dist;
			to[i]=ub;
			adj[i].pb(to[i]);
			adj[to[i]].pb(i);
			//cerr<<i<<' '<<to[i]<<' '<<w[i]<<'\n';
		}
		for(int i=0;i<m;i++)
		{
			ll pos = apple[i];
			int ub = upper_bound(people.begin(),people.end(),pos)-people.begin();
			ub--;
			if(ub<0)
			{
				ub=int(people.size())-1;
			}
			ll dist = D(people[ub],apple[i]);
			apples[ub].pb(dist);
		}
		//get the cycles
		for(int i=0;i<n;i++)
		{
			if(!visited[i])
			{
				path.clear();
				getcycles(i);
			}
		}
		//all cycles are stored now
		//get the trees
		vector<ii> QQ;
		int q; 
		if(!DEBUG) cin>>q;
		else 
		{
			if(n==0) q=0;
			else q = rand()%50+1;
		}
		for(int i=0;i<q;i++) ans[i]=ans2[i]=0;
		for(int z=0;z<q;z++)
		{
			int p; ll t; 
			if(!DEBUG)
			{
				cin>>p>>t;
				p--;
			}
			else
			{
				p=rand()%n;
				t=rand()%50+1;
			}
			if(DEBUG)
			{
				vi curpos=people;
				vi nxtapple(L,ll(1e18)+10);
				for(int i=0;i<m;i++)
				{
					nxtapple[apple[i]]=0;
				}
				ll ans=0;
				for(ll i=0;i<t;i++)
				{
					for(int i=0;i<n;i++)
					{
						curpos[i]++;
						if(curpos[i]>=L) curpos[i]-=L;
					}
					for(int j=0;j<n;j++)
					{
						if(nxtapple[curpos[j]]<=i)
						{
							if(j==p) ans++;
							nxtapple[curpos[j]]=i+C;
						}
					}					
				}
				ans2[z]=ans;
				QQ.pb({p,t});
			}
			queries[p].pb({t,z});
		}
		for(int i=0;i<n;i++)
		{
			if(iscyc[i])
			{
				dfs(i);
			}
		}
		for(int i=0;i<n;i++)
		{
			for(ll &v:T[i])
			{
				if(subsize[v]>subsize[T[i][0]])
				{
					swap(v,T[i][0]);
				}
			}
		}
		//let's check if it works first
		//naively push everything from the trees?
		//later optimize to dsu on tree
		for(int i=0;i<n;i++)
		{
			if(iscyc[i])
			{
				getA(i);
			}
		}
		//stuff on tree, use dsu on tree
		/*
		for(int i=0;i<n;i++)
		{
			cerr<<i<<' '<<shift[i]<<'\n';
			for(ii x:(*A[i])) cerr<<x.fi<<'\n';
		}
		*/
		//stuff on cycle, store 2 sets bruh
		for(int i=0;i<cycles.size();i++)
		{
			vi cyc = cycles[i];
			ll cyclen = 0;
			for(int nd:cyc) cyclen+=w[nd];
			vector<pair<ll,ll> > mods;
			vector<ll> coords;
			{
				ll curw = 0;
				for(int j=0;j<cyc.size();j++)
				{
					for(ii x:(*A[cyc[j]])) 
					{
						coords.pb(x.fi+shift[cyc[j]]-curw);
						mods.pb({md(x.fi+shift[cyc[j]]-curw,cyclen),x.se});
					}
					curw+=w[cyc[j]];
				}
			}
			{
				ll curw = cyclen;
				for(int j=int(cyc.size())-1;j>0;j--)
				{
					curw-=w[cyc[j]];
					for(ii x:(*A[cyc[j]])) mods.pb({md(x.fi+shift[cyc[j]]-curw+cyclen,cyclen),x.se});
				}
			}
			sort(mods.begin(),mods.end());
			mods.erase(unique(mods.begin(),mods.end()),mods.end());
			sort(coords.begin(),coords.end());
			coords.erase(unique(coords.begin(),coords.end()),coords.end());
			Fenwick fen(coords.size()+10);
			Fenwick fen2(coords.size()+10);
			{
				vector<ll> V;
				ll curw = 0;
				for(int j=0;j<cyc.size();j++)
				{
					for(ii x:(*A[cyc[j]])) 
					{
						int id = lower_bound(coords.begin(),coords.end(),x.fi+shift[cyc[j]]-curw)-coords.begin();
						fen.update(id+1,flr(x.fi+shift[cyc[j]]-curw,cyclen));
						fen2.update(id+1,1);
						//cerr<<"INSERT "<<x.fi-curw<<' '<<id<<' '<<flr(x.fi-curw,cyclen)<<' '<<md(x.fi-curw,cyclen)<<'\n';
						int lb = lower_bound(mods.begin(),mods.end(),mp(md(x.fi+shift[cyc[j]]-curw,cyclen),x.se))-mods.begin();
						update(1,0,int(coords.size()),id,lb);
					}
					//V.pb(x.fi-curw);
					for(ii qry:queries[cyc[j]])
					{
						int lab = qry.se;
						ll T = qry.fi;
						T-=curw;
						int id = upper_bound(coords.begin(),coords.end(),T)-coords.begin();
						id--;
						if(id>=0)
						{
							int ub = upper_bound(mods.begin(),mods.end(),mp(md(T,cyclen)+1,-1LL))-mods.begin();
							ans[lab]+=(flr(T,cyclen)+1)*1LL*fen2.query(id+1) - fen.query(id+1) - query(1,0,int(coords.size()),0,id+1,ub);
						}
					}
					curw+=w[cyc[j]];
				}
				//fen = Fenwick(coords.size()+10);
				//fen2 = Fenwick(coords.size()+10);
			}
			for(int nd:affected){mx[nd]=0; st[nd].clear();}
			affected.clear();
			coords.clear();
			{
				ll curw = cyclen;
				for(int j=int(cyc.size())-1;j>0;j--)
				{
					curw-=w[cyc[j]];
					for(ii x:(*A[cyc[j]])) coords.pb(x.fi+shift[cyc[j]]-curw+cyclen);
				}
			}
			sort(coords.begin(),coords.end());
			coords.erase(unique(coords.begin(),coords.end()),coords.end());
			fen = Fenwick(coords.size()+10);
			fen2 = Fenwick(coords.size()+10);
			
			{
				vector<ll> V;
				ll curw = cyclen;
				for(int j=int(cyc.size())-1;j>0;j--)
				{
					curw-=w[cyc[j]];
					for(ii x:(*A[cyc[j]])) 
					{
						int id = lower_bound(coords.begin(),coords.end(),x.fi+shift[cyc[j]]-curw+cyclen)-coords.begin();
						fen.update(id+1,flr(x.fi+shift[cyc[j]]-curw+cyclen,cyclen));
						fen2.update(id+1,1);
						int lb = lower_bound(mods.begin(),mods.end(),mp(md(x.fi+shift[cyc[j]]-curw+cyclen,cyclen),x.se))-mods.begin();
						//cerr<<"INSERT "<<x.fi-curw+cyclen<<' '<<id<<' '<<flr(x.fi-curw+cyclen,cyclen)<<' '<<md(x.fi-curw+cyclen,cyclen)<<'\n';
						update(1,0,int(coords.size()),id,lb);
					}
					for(ii qry:queries[cyc[j-1]])
					{
						int lab = qry.se;
						ll T = qry.fi;
						T-=curw-w[cyc[j-1]];
						int id = upper_bound(coords.begin(),coords.end(),T)-coords.begin();
						id--;
						if(id>=0)
						{
							//cerr<<lab<<' '<<"T: "<<T<<' '<<(flr(T,cyclen)+1)*1LL*fen2.query(id+1) - fen.query(id+1) - query(1,0,int(coords.size()),0,id+1,md(T,cyclen))<<'\n';
							//cerr<<query(1,0,int(coords.size()),0,id+1,md(T,cyclen))<<' '<<fen2.query(id+1)<<' '<<fen.query(id+1)<<'\n';
							int ub = upper_bound(mods.begin(),mods.end(),mp(md(T,cyclen)+1,-1LL))-mods.begin();
							ans[lab]+=(flr(T,cyclen)+1)*1LL*fen2.query(id+1) - fen.query(id+1) - query(1,0,int(coords.size()),0,id+1,ub);
						}
						/*
						for(ll x:V)
						{
							if(T>=x) ans[lab]+=flr(T,cyclen) - flr(x,cyclen) - (md(T,cyclen)<md(x,cyclen)) + 1;
						}
						*/
					}
				}
			}
			for(int nd:affected) {mx[nd]=0;st[nd].clear();}
			affected.clear();
		}	
		if(!DEBUG)
		{
			for(int z=0;z<q;z++)
			{
				cout<<ans[z]<<'\n';
			}
			return 0;
		}
		for(int z=0;z<q;z++)
		{
			if(ans2[z]!=ans[z])
			{
				cerr<<"FAIL AT "<<z<<" ans = "<<ans[z]<<" ans2 = "<<ans2[z]<<'\n';
				freopen("harvest-fail.out","w",stdout);
				cout<<n<<' '<<m<<' '<<L<<' '<<C<<'\n';
				for(int i=0;i<n;i++) cout<<people[i]<<' ';
				cout<<'\n';
				for(int i=0;i<m;i++) cout<<apple[i]<<' ';
				cout<<'\n';
				cout<<q<<'\n';
				for(ii x:QQ) cout<<x.fi+1<<' '<<x.se<<'\n';
				return 0;
			}
		}
		cerr<<"Case #"<<cc<<" complete\n";
	}
}

Compilation message (stderr)

harvest.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
harvest.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
harvest.cpp: In function 'int main()':
harvest.cpp:384:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<cycles.size();i++)
               ~^~~~~~~~~~~~~~
harvest.cpp:393:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<cyc.size();j++)
                 ~^~~~~~~~~~~
harvest.cpp:420:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<cyc.size();j++)
                 ~^~~~~~~~~~~
harvest.cpp:520:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("harvest-fail.out","w",stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 75 / 75