oj.uz

Submission #212259

# Submission time Handle Problem Language Result Execution time Memory
212259 2020-03-22T16:00:50 Z zscoder Harvest (JOI20_harvest) C++17
100 / 100
 4006 ms 405008 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 84856 KB Output is correct
2 Correct 88 ms 85880 KB Output is correct
3 Correct 108 ms 88048 KB Output is correct
4 Correct 97 ms 87780 KB Output is correct
5 Correct 99 ms 88088 KB Output is correct
6 Correct 96 ms 88176 KB Output is correct
7 Correct 99 ms 88176 KB Output is correct
8 Correct 96 ms 87928 KB Output is correct
9 Correct 98 ms 87928 KB Output is correct
10 Correct 103 ms 87924 KB Output is correct
11 Correct 95 ms 87924 KB Output is correct
12 Correct 104 ms 88560 KB Output is correct
13 Correct 107 ms 88564 KB Output is correct
14 Correct 106 ms 87288 KB Output is correct
15 Correct 96 ms 87924 KB Output is correct
16 Correct 99 ms 87924 KB Output is correct
17 Correct 95 ms 87920 KB Output is correct
18 Correct 101 ms 87924 KB Output is correct
19 Correct 103 ms 88036 KB Output is correct
20 Correct 96 ms 88048 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 96936 KB Output is correct
2 Correct 381 ms 125284 KB Output is correct
3 Correct 351 ms 142424 KB Output is correct
4 Correct 387 ms 144800 KB Output is correct
5 Correct 369 ms 149860 KB Output is correct
6 Correct 406 ms 149904 KB Output is correct
7 Correct 306 ms 136804 KB Output is correct
8 Correct 316 ms 136880 KB Output is correct
9 Correct 549 ms 172224 KB Output is correct
10 Correct 403 ms 171352 KB Output is correct
11 Correct 624 ms 171076 KB Output is correct
12 Correct 605 ms 171076 KB Output is correct
13 Correct 612 ms 171072 KB Output is correct
14 Correct 438 ms 170292 KB Output is correct
15 Correct 535 ms 154596 KB Output is correct
16 Correct 353 ms 132196 KB Output is correct
17 Correct 353 ms 131936 KB Output is correct
18 Correct 227 ms 105712 KB Output is correct
19 Correct 247 ms 105712 KB Output is correct
20 Correct 341 ms 128996 KB Output is correct

Subtask #3
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 84856 KB Output is correct
2 Correct 88 ms 85880 KB Output is correct
3 Correct 108 ms 88048 KB Output is correct
4 Correct 97 ms 87780 KB Output is correct
5 Correct 99 ms 88088 KB Output is correct
6 Correct 96 ms 88176 KB Output is correct
7 Correct 99 ms 88176 KB Output is correct
8 Correct 96 ms 87928 KB Output is correct
9 Correct 98 ms 87928 KB Output is correct
10 Correct 103 ms 87924 KB Output is correct
11 Correct 95 ms 87924 KB Output is correct
12 Correct 104 ms 88560 KB Output is correct
13 Correct 107 ms 88564 KB Output is correct
14 Correct 106 ms 87288 KB Output is correct
15 Correct 96 ms 87924 KB Output is correct
16 Correct 99 ms 87924 KB Output is correct
17 Correct 95 ms 87920 KB Output is correct
18 Correct 101 ms 87924 KB Output is correct
19 Correct 103 ms 88036 KB Output is correct
20 Correct 96 ms 88048 KB Output is correct
21 Correct 213 ms 96936 KB Output is correct
22 Correct 381 ms 125284 KB Output is correct
23 Correct 351 ms 142424 KB Output is correct
24 Correct 387 ms 144800 KB Output is correct
25 Correct 369 ms 149860 KB Output is correct
26 Correct 406 ms 149904 KB Output is correct
27 Correct 306 ms 136804 KB Output is correct
28 Correct 316 ms 136880 KB Output is correct
29 Correct 549 ms 172224 KB Output is correct
30 Correct 403 ms 171352 KB Output is correct
31 Correct 624 ms 171076 KB Output is correct
32 Correct 605 ms 171076 KB Output is correct
33 Correct 612 ms 171072 KB Output is correct
34 Correct 438 ms 170292 KB Output is correct
35 Correct 535 ms 154596 KB Output is correct
36 Correct 353 ms 132196 KB Output is correct
37 Correct 353 ms 131936 KB Output is correct
38 Correct 227 ms 105712 KB Output is correct
39 Correct 247 ms 105712 KB Output is correct
40 Correct 341 ms 128996 KB Output is correct
41 Correct 3441 ms 361240 KB Output is correct
42 Correct 498 ms 159952 KB Output is correct
43 Correct 325 ms 143700 KB Output is correct
44 Correct 2175 ms 370392 KB Output is correct
45 Correct 1919 ms 379956 KB Output is correct
46 Correct 1939 ms 373276 KB Output is correct
47 Correct 1972 ms 374004 KB Output is correct
48 Correct 2041 ms 377620 KB Output is correct
49 Correct 1921 ms 378044 KB Output is correct
50 Correct 1945 ms 367488 KB Output is correct
51 Correct 1908 ms 367452 KB Output is correct
52 Correct 3845 ms 404996 KB Output is correct
53 Correct 4006 ms 404560 KB Output is correct
54 Correct 3890 ms 405008 KB Output is correct
55 Correct 3724 ms 404996 KB Output is correct
56 Correct 2031 ms 364416 KB Output is correct
57 Correct 2025 ms 362200 KB Output is correct
58 Correct 2075 ms 364240 KB Output is correct
59 Correct 2021 ms 361676 KB Output is correct
60 Correct 1909 ms 362104 KB Output is correct
61 Correct 1911 ms 362480 KB Output is correct
62 Correct 3593 ms 272608 KB Output is correct
63 Correct 1720 ms 335072 KB Output is correct
64 Correct 1779 ms 335012 KB Output is correct
65 Correct 1634 ms 335208 KB Output is correct
66 Correct 1767 ms 334300 KB Output is correct
67 Correct 1746 ms 334224 KB Output is correct
68 Correct 1750 ms 334208 KB Output is correct
69 Correct 3190 ms 361904 KB Output is correct
70 Correct 3379 ms 362404 KB Output is correct
71 Correct 2464 ms 357276 KB Output is correct
72 Correct 1920 ms 356160 KB Output is correct