Submission #1086182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086182		t9unkubj	Harvest (JOI20_harvest)	C++17	0 / 100	316 ms	11384 KiB

harvest

#ifdef t9unkubj
#include"template.h"
//#include"template_no_debug.h"
#else
#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
#define dbg(...) 199958
using namespace std;
#include<bits/stdc++.h>
using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
template<class T>using vvvc=vvc<vc<T>>;
using vi=vc<int>;
using vvi=vc<vi>;
using vvvi=vc<vvi>;
using vl=vc<ll>;
using vvl=vc<vl>;
using vvvl=vc<vvl>;
template<class T>using smpq=priority_queue<T,vector<T>,greater<T>>;
template<class T>using bipq=priority_queue<T>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define is insert
#define bg begin()
#define ed end()
void scan(int&a) { cin >> a; }
void scan(ll&a) { cin >> a; }
void scan(string&a) { cin >> a; }
void scan(char&a) { cin >> a; }
void scan(uint&a) { cin >> a; }
void scan(ull&a) { cin >> a; }
void scan(bool&a) { cin >> a; }
void scan(ld&a){ cin>> a;}
template<class T> void scan(vector<T>&a) { for(auto&x:a) scan(x); }
void read() {}
template<class Head, class... Tail> void read(Head&head, Tail&... tail) { scan(head); read(tail...); }
#define INT(...) int __VA_ARGS__; read(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; read(__VA_ARGS__);
#define ULL(...) ull __VA_ARGS__; read(__VA_ARGS__);
#define STR(...) string __VA_ARGS__; read(__VA_ARGS__);
#define CHR(...) char __VA_ARGS__; read(__VA_ARGS__);
#define DBL(...) double __VA_ARGS__; read(__VA_ARGS__);
#define LD(...) ld __VA_ARGS__; read(__VA_ARGS__);
#define VC(type, name, ...) vector<type> name(__VA_ARGS__); read(name);
#define VVC(type, name, size, ...) vector<vector<type>> name(size, vector<type>(__VA_ARGS__)); read(name);
void print(int a) { cout << a; }
void print(ll a) { cout << a; }
void print(string a) { cout << a; }
void print(char a) { cout << a; }
void print(uint a) { cout << a; }
void print(bool a) { cout << a; }
void print(ull a) { cout << a; }
void print(double a) { cout << a; }
void print(ld a){ cout<< a; }
template<class T> void print(vector<T>a) { for(int i=0;i<(int)a.size();i++){if(i)cout<<" ";print(a[i]);}cout<<endl;}
void PRT() { cout <<endl; return ; }
template<class T> void PRT(T a) { print(a); cout <<endl; return; }
template<class Head, class... Tail> void PRT(Head head, Tail ... tail) { print(head); cout << " "; PRT(tail...); return; }
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
void YesNo(bool b){
    cout<<(b?"Yes":"No")<<endl;
}
void Yes(){
    cout<<"Yes"<<endl;
}
void No(){
    cout<<"No"<<endl;
}
template<class T>
int popcount(T n){
    return __builtin_popcountll(n);
}
template<class T>
T sum(vc<T>&a){
    return accumulate(all(a),T(0));
}
template<class T>
T max(vc<T>&a){
    return *max_element(all(a));
}
template<class T>
T min(vc<T>&a){
    return *min_element(all(a));
}
template<class T>
void unique(vc<T>&a){
    a.erase(unique(all(a)),a.end());
}
vvi readgraph(int n,int m,int off = -1){
    vvi g(n);
    rep(i, m){
        int u,v;
        cin>>u>>v;
        u+=off,v+=off;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    return g;
}
vvi readtree(int n,int off=-1){
    return readgraph(n,n-1,off);
}
template<class T>
vc<T> presum(vc<T> &a){
    vc<T> ret(a.size()+1);
    rep(i,a.size())ret[i+1]=ret[i]+a[i];
    return ret;
}
template<class T, class F>
vc<T> &operator+=(vc<T> &a,F b){
    for (auto&v:a)v += b;
    return a;
}
template<class T, class F>
vc<T> &operator-=(vc<T>&a,F b){
    for (auto&v:a)v-=b;
    return a;
}
template<class T, class F>
vc<T> &operator*=(vc<T>&a,F b){
    for (auto&v:a)v*=b;
    return a;
}
#endif
double pass_time=0;
//k以下のnum
struct range_tree_get_num{
	int n;
    struct S{
        vc<ll>seq;
        vc<ll>pre;
        void build(const vc<ll>&c){
            seq=c;
            pre=presum(pre);
        }
        int size(){
            return seq.size();
        }
    };
	vector<S>node;
    range_tree_get_num(){}
	range_tree_get_num(int N){
		int log=0;
		while((1<<log)<=N)log++;
		n=1<<log;
		node=vector<S>(n*2);
	}
	S merge(S&a,S&b){
        S c;
		int l=0,r=0;
		while(l<(int)a.size()||r<(int)b.size()){
			if(l==(int)a.size())c.seq.push_back(b.seq[r++]);
			else if(r==(int)b.size())c.seq.push_back(a.seq[l++]);
			else if(a.seq[l]<=b.seq[r])c.seq.push_back(a.seq[l++]);
			else c.seq.push_back(b.seq[r++]);
		}
        c.build(c.seq);
		return c;
	}
	void set(int i,vl t){
        S c;
        c.build({t});
		node[i+n]=c;
	}
	void build(){
		for(int i=node.size();i;i--){
			int a=i*2,b=i*2+1;
			if(b<(int)node.size()){
				node[i]=merge(node[a],node[b]);
			}
		}	
	}
	ll op(ll l,S&c){
        return upper_bound(all(c.seq),l)-c.seq.bg;
        
	}
	ll prod(int l,int r,ll x){
		l+=n,r+=n;

		ll res=0;

		while(l<r){
			if(l&1)res+=op(x,node[l++]);
			if(r&1)res+=op(x,node[--r]);
			l>>=1,r>>=1;
		}
		return res;
	}	
};

struct range_tree_sum{
	int n;
    struct S{
        vc<ll>seq;
        vc<ll>pre;
        void build(const vc<ll>&c){
            seq=c;
            pre=presum(seq);
        }
        int size(){
            return seq.size();
        }
    };
	vector<S>node;
    range_tree_sum(){}
	range_tree_sum(int N){
		int log=0;
		while((1<<log)<=N)log++;
		n=1<<log;
		node=vector<S>(n*2);
	}
	S merge(S&a,S&b){
        S c;
		int l=0,r=0;
		while(l<(int)a.size()||r<(int)b.size()){
			if(l==(int)a.size())c.seq.push_back(b.seq[r++]);
			else if(r==(int)b.size())c.seq.push_back(a.seq[l++]);
			else if(a.seq[l]<=b.seq[r])c.seq.push_back(a.seq[l++]);
			else c.seq.push_back(b.seq[r++]);
		}
        c.build(c.seq);
		return c;
	}
	void set(int i,vl t){
        S c;
        c.build({t});
		node[i+n]=c;
	}
	void build(){
		for(int i=node.size();i;i--){
			int a=i*2,b=i*2+1;
			if(b<(int)node.size()){
				node[i]=merge(node[a],node[b]);
			}
		}	
	}
    ll op2(ll l,S&c){
        return upper_bound(all(c.seq),l)-c.seq.bg;
    }
    ll counter(int l,int r,ll x){
        l+=n,r+=n;

		ll res=0;

		while(l<r){
			if(l&1)res+=op2(x,node[l++]);
			if(r&1)res+=op2(x,node[--r]);
			l>>=1,r>>=1;
		}
		return res;
    }
    
	ll op(ll l,S&c){
        auto itr=upper_bound(all(c.seq),l)-c.seq.bg;
        return c.pre[itr];
	}
	ll prod(int l,int r,ll x){
		l+=n,r+=n;

		ll res=0;

		while(l<r){
			if(l&1)res+=op(x,node[l++]);
			if(r&1)res+=op(x,node[--r]);
			l>>=1,r>>=1;
		}
		return res;
	}	
};
template<class T,auto op,int extra>
struct base_dsu{
        vector<int>par;
        vector<T>data;
        base_dsu(int n):par(n,-1){
            static_assert(!extra,"e is needed");
        }
        base_dsu(int n,T e):par(n,-1),data(n,e){}
        T& operator[](int i){
            static_assert(extra,"No data");
            return data[leader(i)];
        }
        int root(int x){
            if(par[x]<0)return x;
            else return par[x]=root(par[x]);
        }
        bool same(int x,int y){
            return root(x)==root(y);
        }
        bool merge(int x,int y){
            x=root(x);
            y=root(y);
            if(x==y)return false;
            if(par[x]>par[y])swap(x,y);
            par[x]+=par[y];
            par[y]=x;
            if(extra){
                data[x]=op(data[y],data[x]);
            }
            return true;
        }
        int size(int x){
            return -par[root(x)];
        }
        int leader(int x){
            return root(x);
        }

};
int tf323(int a,int b){return a;}
using dsu=base_dsu<int,tf323,0>;
template<class T,auto op>
using extra_dsu=base_dsu<T,op,1>;
int op(int a,int b){
    return max(a,b);
}
void solve(){
    LL(n,m,l,c);
    VC(ll,a,n);
    VC(ll,b,m);
    a-=1,b-=1;
    vc<pll> to(n);
    dbg(c%l);
    //graphを作る
    {
        auto A=a;
        for(auto&x:a)A.pb(x+l);
        rep(i,n){
            ll nxt=a[i]-c+l*2e9;
            auto itr=upper_bound(all(A),nxt%l)-1-A.bg;
            if(itr<0)itr+=n;
            itr%=n;
            to[i].se=c+abs(a[itr]-(nxt%l));
            to[i].fi=itr;
            assert(to[i].fi>=0);
            dbg(to[i]);
        }
    } 
    //初期にいる場所とコスト
    vvl gs(n);
    {
        vc<array<ll,3>>events;
        rep(i,n){
            events.pb({a[i],i,0});
            events.pb({a[i]+l,i,0});
        }
        rep(i,m){
            events.pb({b[i],i,1});
            events.pb({b[i]+l,i,1});
        }
        sort(all(events));
        ll last=-1;
        ll pos=-1;
        vi seen(m);
        for(auto [x,i,t]:events){
            if(t==0){
                last=i;
                pos=x;
            }else{
                if(last==-1)continue;
                if(seen[i])continue;
                seen[i]=1;
                gs[last].pb(abs(x-pos));
            }
        }
    }
    rep(i,n)dbg(gs[i]);
    //rep(i,n)dbg(gs[i]);
    ///サイクルを作る
    vi is_cycle(n);

    extra_dsu<int,op> dsu(n,-1);
    {
        rep(i,n){
            if(!dsu.merge(i,to[i].fi)){
                int now=i;
                while(!is_cycle[now]){
                    is_cycle[now]=1;
                    now=to[now].fi;
                }
            }
        }
    }
    vvc<pii> inv(n);
    rep(i,n)inv[to[i].fi].pb({i,to[i].se});
    //euler tour
    vi in(n,-1);
    vi out(n,-1);
    int now_time__=0;
    function<void(int)>dfs=[&](int now){
        in[now]=now_time__++;
        for(auto&[x,w]:inv[now]){
            if(in[x]==-1){
                dfs(x);
            }
        }
        out[now]=now_time__;
    };
    rep(i,n){
        if(in[i]==-1&&is_cycle[i])dfs(i);
    }
    //パスを考える

    rep(i,n){
        if(is_cycle[i]){
            dsu[i]=i;
        }
    }
    vl md_to_cycle(n,1e18);
    vl from(n,-1);
    queue<array<ll,3>>que;
    rep(i,n){
        if(is_cycle[i]){
            md_to_cycle[i]=0;
            que.push({0,i,i});
            from[i]=i;
        } 
    }
    while(que.size()){
        auto [p,q,r]=que.front();que.pop();
        for(auto&[x,w]:inv[q]){
            if(chmin(md_to_cycle[x],p+w)){
                from[x]=r;
                que.push({md_to_cycle[x],x,r});
            }
        }
    }
    dbg(md_to_cycle);
    vvl cycle_vs(n);//サイクル上のここに来るまでのコスト
    rep(i,n){
        for(auto&x:gs[i]){
            dbg(i,x);
            cycle_vs[from[i]].pb(x+md_to_cycle[i]);
        }
    }
    //全部leaderにそろえる
    vl md_to_leader(n,1e18);
    rep(i,n){
        if(dsu[i]==i){
            md_to_leader[i]=0;
            que.push({0,i,i});
        }
    }

    while(que.size()){
        auto [p,q,hogehoge]=que.front();que.pop();
        for(auto&[x,w]:inv[q]){
            if(chmin(md_to_leader[x],p+w)){
                que.push({md_to_leader[x],x,hogehoge});
            }
        }
    }
    //leaderから出発したき
    vl md_from_leader(n,1e18);
    rep(i,n){
        if(dsu[i]==i){
            md_from_leader[i]=0;
            que.push({0,i,i});
        }
    }
    while(que.size()){
        auto [p,q,hogehoge]=que.front();que.pop();
        {
            ll x=to[q].fi,w=to[q].se;
            if(chmin(md_from_leader[x],p+w)){
                que.push({md_from_leader[x],x,hogehoge});
            }
        }
    }
    dbg(md_from_leader);
    //1サイクル当たり
    vl cycle_w(n,c);
    rep(i,n){
        if(is_cycle[i]){
            ll x=to[i].fi,y=to[i].se;
            chmax(cycle_w[dsu[i]],md_from_leader[i]+y);
        }
    }
    dbg(md_to_leader);
    //まとめる
    vvl vs_leader(n);
    rep(i,n){
        if(is_cycle[i]){
            for(auto&x:cycle_vs[i]){
                vs_leader[dsu[i]].pb(x+md_to_leader[i]);
            }
        }
    }
    
    dbg(cycle_w);
    dbg(vs_leader[4]);
    rep(i,n){
        sort(all(vs_leader[i]),[&](auto a,auto b){
            return a%cycle_w[i]<b%cycle_w[i];
        });
    }
    //部分木に対してクエリ，eulerツアー順，md_to_cycle[i]を足す
    range_tree_get_num rt(n);
    rep(i,n){
        gs[i]+=md_to_cycle[i];
        if(gs[i].size())rt.set(in[i],gs[i]);
    }
    rt.build();
    using R=range_tree_sum;
    vc<R>leader_rt_down(n);
    vc<R>leader_rt_up(n);
    rep(i,n){
        if(dsu[i]!=i)continue;
        leader_rt_down[i]=leader_rt_up[i]=R(vs_leader[i].size());
        rep(j,vs_leader[i].size())leader_rt_down[i].set(j,{vs_leader[i][j]/cycle_w[dsu[i]]}),leader_rt_up[i].set(j,{(vs_leader[i][j]+cycle_w[dsu[i]]-1)/cycle_w[dsu[i]]});
        leader_rt_down[i].build();
        leader_rt_up[i].build();
    }

    
    //cycleをseg木に並べる
    vi in_cycle(n,-1);
    vi left(n,1e9);
    int now_time=0;

    rep(i,n){
        if(dsu[i]==i){
            int now=i;
            do{
                in_cycle[now]=now_time++;
                chmin(left[i],now_time);
                now=to[now].fi;
            }while(now!=i);
        } 
    }
    
    dbg(in_cycle);
    dbg(vs_leader[4]);
    range_tree_get_num rt3(n);
    rep(i,n){
        if(is_cycle[i]){
            dbg(cycle_vs[i]);
            cycle_vs[i]+=md_to_leader[i];
            if(cycle_vs[i].size())rt3.set(in_cycle[i],cycle_vs[i]);
            cycle_vs[i]+=-md_to_leader[i];
        }
    }
    rt3.build();
    INT(q);
    dbg(in,out);
    while(q--){
        LL(x,t);
        --x;
        if(is_cycle[x]){
            ll r=dsu[x];
            ll L=cycle_w[r];
            ll ans=0;
            //[0,ac]がt未満のあまり
            t-=md_from_leader[x];
            ll ac=-1,wa=vs_leader[r].size();
            while(wa-ac>1){
                ll wj=ac+wa>>1;
                if(vs_leader[r][wj]%L<=t%L){
                    ac=wj;
                }else{
                    wa=wj;
                }
            }
            //t/L以下のsum,そのままできる
            //ans+=(ac+1)*(t/L+1)-(leader_rt_down[r].prod(0,ac+1,t/L));
            ans+=leader_rt_down[r].counter(0,ac+1,t/L)*(t/L+1)-(leader_rt_down[r].prod(0,ac+1,t/L));
            //[ac+1,をみる
            int sz=vs_leader[r].size();
            //ans+=(sz-(ac+1)+1)*((t+L-1)/L+1)-(leader_rt_up[r].prod(ac+1,sz,(t+L-1)/L));
            ans+=leader_rt_up[r].counter(ac+1,sz,t/L)*(t/L+1)-(leader_rt_up[r].prod(ac+1,sz,t/L));
            //ans+=leader_rt_up[r].counter(ac+1,sz,(t+L-1)/L)*((t+L-1)/L+1)-(leader_rt_up[r].prod(ac+1,sz,(t+L-1)/L));
            t+=md_from_leader[x];
            //こっちに入っているやつのうちvalidなもの
            ans+=rt3.prod(left[r],in_cycle[x]+1,t+md_to_leader[x]);
            //dbg(left[r],in_cycle[x]+1,x,rt3.prod(left[r],in_cycle[x]+1,t+md_to_leader[x]));
            PRT(ans);
        }else{
            int l=in[x],r=out[x];
            auto res=rt.prod(l,r,md_to_cycle[x]+t);

            PRT(res); 
        }
    }
}
signed main(){
    #ifdef t9unkubj
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    cin.tie(0)->sync_with_stdio(0);
    pass_time=clock();
    int t=1;
    //cin>>t;
    while(t--)solve();
    pass_time=clock()-pass_time;
    dbg(pass_time/CLOCKS_PER_SEC);
}

Compilation message (stderr)

harvest.cpp: In function 'void solve()':
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define dbg(...) 199958
      |                  ^~~~~~
harvest.cpp:352:5: note: in expansion of macro 'dbg'
  352 |     dbg(c%l);
      |     ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define dbg(...) 199958
      |                  ^~~~~~
harvest.cpp:365:13: note: in expansion of macro 'dbg'
  365 |             dbg(to[i]);
      |             ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define dbg(...) 199958
      |                  ^~~~~~
harvest.cpp:396:13: note: in expansion of macro 'dbg'
  396 |     rep(i,n)dbg(gs[i]);
      |             ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define dbg(...) 199958
      |                  ^~~~~~
harvest.cpp:457:5: note: in expansion of macro 'dbg'
  457 |     dbg(md_to_cycle);
      |     ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define dbg(...) 199958
      |                  ^~~~~~
harvest.cpp:461:13: note: in expansion of macro 'dbg'
  461 |             dbg(i,x);
      |             ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define dbg(...) 199958
      |                  ^~~~~~
harvest.cpp:499:5: note: in expansion of macro 'dbg'
  499 |     dbg(md_from_leader);
      |     ^~~
harvest.cpp:504:16: warning: unused variable 'x' [-Wunused-variable]
  504 |             ll x=to[i].fi,y=to[i].se;
      |                ^
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define dbg(...) 199958
      |                  ^~~~~~
harvest.cpp:508:5: note: in expansion of macro 'dbg'
  508 |     dbg(md_to_leader);
      |     ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define dbg(...) 199958
      |                  ^~~~~~
harvest.cpp:519:5: note: in expansion of macro 'dbg'
  519 |     dbg(cycle_w);
      |     ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define dbg(...) 199958
      |                  ^~~~~~
harvest.cpp:520:5: note: in expansion of macro 'dbg'
  520 |     dbg(vs_leader[4]);
      |     ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define dbg(...) 199958
      |                  ^~~~~~
harvest.cpp:561:5: note: in expansion of macro 'dbg'
  561 |     dbg(in_cycle);
      |     ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define dbg(...) 199958
      |                  ^~~~~~
harvest.cpp:562:5: note: in expansion of macro 'dbg'
  562 |     dbg(vs_leader[4]);
      |     ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define dbg(...) 199958
      |                  ^~~~~~
harvest.cpp:566:13: note: in expansion of macro 'dbg'
  566 |             dbg(cycle_vs[i]);
      |             ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define dbg(...) 199958
      |                  ^~~~~~
harvest.cpp:574:5: note: in expansion of macro 'dbg'
  574 |     dbg(in,out);
      |     ^~~
harvest.cpp:586:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  586 |                 ll wj=ac+wa>>1;
      |                       ~~^~~
harvest.cpp: In function 'int main()':
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define dbg(...) 199958
      |                  ^~~~~~
harvest.cpp:625:5: note: in expansion of macro 'dbg'
  625 |     dbg(pass_time/CLOCKS_PER_SEC);
      |     ^~~

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