Submission #261604

#	Time	Username	Problem	Language	Result	Execution time	Memory
261604		shayan_p	Harvest (JOI20_harvest)	C++14	100 / 100	704 ms	113804 KiB

harvest

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define norm(x, m) ((((x) % (m)) + (m)) % (m))

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 4e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

struct fenwick{
    ll fn[maxn], TOT; // over flow nakone!
    vector<int> done;
    void add(int pos, ll x){
	TOT+= x;
	for(pos+= 3; pos < maxn; pos+= (pos & -pos))
	    done.PB(pos), fn[pos]+= x;
    }
    ll ask(int pos){
	ll ans = 0;
	for(pos+= 3; pos > 0; pos-= (pos & -pos))
	    ans+= fn[pos];
	return ans;
    }
    ll askG(int pos){
	return TOT - ask(pos-1);
    }
    void restart(){
	TOT = 0;
	while(sz(done)){
	    fn[done.back()] = 0;
	    done.pop_back();
	}
    }
};// restart ham bayad dashte bashe
fenwick fen, fen2;

int a[maxn], b[maxn], f[maxn], fl[maxn], n;

int mark[maxn];
vector< pair<int, ll> > qur[maxn];
ll ans[maxn];
vector<int> v[maxn];

int ROOT;
ll dis[maxn];
vector<ll> arr;
void prep(int u){
    if(u >= n)
	arr.PB(dis[u]);
    for(int y : v[u])
	if(y != ROOT)
	    dis[y] = dis[u] + fl[y], prep(y);
}
void dfs(int u){    
    if(u >= n)
	fen.add(LB(arr, dis[u]), 1);
    for(auto x : qur[u])
	ans[x.F]-= fen.ask(UB(arr, x.S + dis[u]) - 1);
    for(int y : v[u])
	if(y != ROOT)
	    dfs(y);
    for(auto x : qur[u])
	ans[x.F]+= fen.ask(UB(arr, x.S + dis[u]) - 1);
}

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

    int m, C, L;
    cin >> n >> m >> L >> C;
    for(int i = 0; i < n; i++)
	cin >> a[i];
    for(int i = 0; i < m; i++)
	cin >> b[i];
    {
	int pt = 0;
	while(pt < m && b[pt] < a[0])
	    f[n + pt] = n-1, fl[n + pt] = L-a[n-1]+b[pt], pt++;
	int pt2 = 0;
	while(pt < m){
	    while(pt2+1 < n && a[pt2 + 1] < b[pt])
		pt2++;
	    f[n + pt] = pt2;
	    fl[n + pt] = b[pt] - a[pt2];
	    pt++;
	}
    }
    {
	for(int i = 0; i < n; i++){
	    int pos = (((a[i] - C) % L) + L) % L;
	    int id = upper_bound(a, a+n, pos) - a;
	    f[i] = (id + n - 1) % n;
	    fl[i] = C + ((((pos - a[f[i]]) % L) + L) % L);
	}	
    }
    
    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
	int u;
	cin >> u;
	ll T;
	cin >> T;
	--u;
	qur[u].PB({i, T});	
    }

    
    vector<int> roots;    
    for(int i = 0; i < n; i++){
	int tmp = i, tmpb = i;
	while(mark[tmp] == 0)
	    mark[tmp] = i+1, tmpb = tmp, tmp = f[tmp];
	if(mark[tmp] == i+1){
	    roots.PB(tmpb);
	}
    }

    for(int i = 0; i < n + m; i++){
	v[f[i]].PB(i);
    }
    for(int u : roots){
	ROOT = u;
	
	fen.restart();
	arr.clear();
	prep(u);
	
	sort(arr.begin(), arr.end());
	vector< pair<ll, int> >arr2;
	for(ll x : arr){
	    if(arr2.empty() || arr2.back().F != x)
		arr2.PB({x, 1});
	    else
		arr2[sz(arr2)-1].S++;
	}
	arr.clear();
	for(auto x : arr2){
	    arr.PB(x.F);
	}
	
	dfs(u);
	int tmp = u;
	ll cyc = 0;

	vector< pair<int, pair<ll, pair<int, ll> > > > tdo;
	
	do{
	    cyc+= fl[tmp];
	    tmp = f[tmp];
	    for(auto x : qur[tmp]){
		tdo.PB( { UB(arr, x.S - cyc), {cyc, x} } );
	    }
	}while(tmp != u);
	
	sort(tdo.begin(), tdo.end());

	fen2.restart();
	vector<ll> arr3;
	for(ll x : arr){
	    arr3.PB(x % cyc);
	}
	sort(arr3.begin(), arr3.end());
	arr3.resize( unique(arr3.begin(), arr3.end()) - arr3.begin() );
	int nw = 0;
	ll cnt = 0, cnt2 = 0;
	for(auto it : tdo){
	    while(nw < it.F){
		fen2.add( LB(arr3, arr[nw] % cyc), arr2[nw].S );
		cnt+= arr2[nw].S;
		cnt2+= 1ll * arr2[nw].S * (arr[nw] / cyc);
		nw++;
	    }
	    auto [id, T] = it.S.S;
	    
	    ll lz = it.S.F;
	    
	    ans[id]+= (1 + T/cyc) * cnt;
	    
	    ans[id]-= cnt2 + 1ll * cnt * (lz / cyc) + fen2.askG( LB(arr3, ((-lz) % cyc) + cyc) );

	    ll L = (T % cyc) + 1, R = cyc-1;

	    if(L <= R){
		L = norm(L - lz, cyc), R = norm(R - lz, cyc);
		
		if(L <= R)
		    ans[id]-= fen2.askG(LB(arr3, L)) - fen2.askG(UB(arr3, R));
		else
		    ans[id]-= fen2.askG(LB(arr3, L)) + fen2.ask(UB(arr3, R) - 1);

	    }
	}

	/*
ll lz = 0;
	do{
	    lz+= fl[tmp];
	    tmp = f[tmp];
	    for(auto x : qur[tmp]){
		for(auto y : arr2){
		    if(x.S >= y.F + lz)
			ans[x.F]+= 1ll * y.S * (((x.S - y.F - lz) / cyc) + 1);
		}
	    }
	    }while(tmp != u);*/
	
    }
    for(int i = 0; i < q; i++){
	cout << ans[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

harvest.cpp: In function 'int main()':
harvest.cpp:185:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
      auto [id, T] = it.S.S;
           ^

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