Submission #1108250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108250		8pete8	Harvest (JOI20_harvest)	C++17	0 / 100	184 ms	117744 KiB

harvest

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=998244353,mxn=4e5+5,inf=1e18,minf=-1e18,lg=30;
//#undef int
int n,k,m,q,c,l;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);
}
int pos[mxn+10],post[mxn+10],pref[mxn+10];
int caldist(int from,int go){
    if(from>go)return from-go;
    return l-go+from;
}
vector<int>adj[mxn+10];
void addedge(int x,int y){
    adj[x].pb(y);
}
int on[mxn+10],vis[mxn+10],oncycle[mxn+10]; //on cycle
int compsz[mxn+10];
vector<int>cycle[mxn+10];
int T=n,cnt=0;
stack<int>st;
void getcycle(int cur){
    if(vis[cur])return;
    vis[cur]=on[cur]=1;
    st.push(cur);
    for(auto i:adj[cur]){
        if(on[i]){
            cnt++;
            while(st.top()!=i)cycle[cnt].pb(st.top()),oncycle[st.top()]=cnt,st.pop();
            cycle[cnt].pb(i),oncycle[i]=cnt;
            reverse(all(cycle[cnt]));
            for(int j=1;j<cycle[cnt].size();j++)compsz[cnt]+=caldist(pos[cycle[cnt][j]],pos[cycle[cnt][j-1]])+(k*l);
            compsz[cnt]+=caldist(pos[i],pos[cur])+(k*l);
        }
        if(!vis[i])getcycle(i);
    }
    on[cur]=0;
    if(!st.empty())st.pop();
}
int dist[mxn+10],sz[mxn+10],tin[mxn+10],tout[mxn+10],who[mxn+10],where[mxn+10];
int curtime=0;
pii cant;
void getdist(int cur){
    sz[cur]=1;
    tin[cur]=++curtime;
    who[tin[cur]]=cur;
    for(auto i:adj[cur])if(cant.f!=cur||cant.s!=i){
        dist[i]=dist[cur]+caldist(pos[i],pos[cur]);
        if(i<=n)dist[i]+=(k*l);
        getdist(i);
        sz[cur]+=sz[i];
    }
    tout[cur]=curtime;
}
vector<pii>qry[mxn+10];
int ans[mxn+10];
struct fen{
    int fwk[mxn+10],sz=0;
    vector<pii>keep;
    void update(int pos,int val){
        pos++;
        keep.pb({pos,val});
        for(int i=pos;i<=sz;i+=(i&-i))fwk[i]+=val;
    }
    int qry(int pos){
        int sum=0;
        pos++;
        for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
        return sum;
    }
    void re(){
        for(auto i:keep)for(int j=i.f;j<=sz;j+=(j&-j))fwk[j]-=i.s;
        keep.clear();
    }
}t,t2;
/*
sack
*/
vector<int>have[mxn+10];
vector<int>comp;
vector<pii>extra[mxn+10];
int cc=0;
void sack(int cur,int keep){
    //solving case where node is not on cycle
    int hvy=0;
    vis[cur]=1;
    for(auto i:adj[cur])if(cur!=cant.f||i!=cant.s){
        if(sz[i]>sz[hvy])hvy=i;
    }
    for(auto i:adj[cur])if((cur!=cant.f||i!=cant.s)&&i!=hvy)sack(i,0);
    if(hvy)sack(hvy,1);
    int x=0;
    for(auto i:adj[cur])if(cur!=cant.f||i!=cant.s){
        if(i!=hvy)for(int j=tin[i];j<=tout[i];j++)if(who[j]>n)t.update(where[who[j]],1);
        if(have[i].size()>have[cur].size())swap(have[cur],have[i]);
        for(auto j:have[i])have[cur].pb(j);
    }
    if(cur>n)t.update(where[cur],1),have[cur].pb(dist[cur]);
    for(auto i:qry[cur]){
        auto it=upper_bound(all(comp),i.f+dist[cur])-comp.begin()-1;
        if(it)ans[i.s]=t.qry(it);
    }
    if(!keep)t.re();
}
/*

*/
int32_t main(){
    fastio
	cin>>n>>m>>l>>c;
	for(int i=1;i<=n;i++)cin>>pos[i];
	for(int i=1;i<=m;i++)cin>>post[i];
	int cur=1;
    k=c/l;
	c%=l;
	for(int i=n+1;i<=2*n;i++)pos[i]=pos[i-n]+l;
	for(int i=n+1;i<=2*n;i++){
		while(pos[i]-pos[cur]>=c)cur++;
		addedge(cur-1-((cur-1>n)?n:0),i-n);
	}
    T=n;
    for(int i=1;i<=n;i++)if(!vis[i])getcycle(i);
    cur=1;
    for(int i=1;i<=m;i++){
        T++;
        while(cur<=n&&post[i]>pos[cur])cur++;
        pos[T]=post[i];
        if(cur==1)addedge(n,T);
        else addedge(cur-1,T);
    }
    for(int i=1;i<=cnt;i++){
        cant={cycle[i].back(),cycle[i][0]};
        getdist(cycle[i][0]);
    }
    for(int i=1;i<=T;i++)comp.pb(dist[i]),vis[i]=0;
    sort(all(comp));
    comp.erase(unique(all(comp)),comp.end());
    t.sz=comp.size();
    for(int i=n+1;i<=T;i++)where[i]=lb(all(comp),dist[i])-comp.begin();
    cin>>q;
    for(int i=0;i<q;i++){
        int v,t;cin>>v>>t;
        qry[v].pb({t,i});
    }
    for(int i=1;i<=cnt;i++){
        cc=i;
        cant={cycle[i].back(),cycle[i][0]};
        sack(cycle[i][0],0);
    }
    vector<pair<pii,int>>qry2;
    for(int i=1;i<=cnt;i++){
        int head=cycle[i][0];
        for(auto j:cycle[i])for(auto k:qry[j])qry2.pb({{k.f,j},k.s});
        sort(all(qry2));
        int sum=0;
        comp.clear();
        for(auto j:have[head])comp.pb(j%compsz[i]);
        for(auto j:qry2)comp.pb(j.f.f%compsz[i]);
        t.sz=comp.size();
        sort(all(comp));
        comp.erase(unique(all(comp)),comp.end());
        cur=0;
        for(auto j:qry2){
            while(cur<have[head].size()&&j.f.f>=have[head][cur]){
                t.update(lb(all(comp),have[head][cur]%compsz[i])-comp.begin(),1);
                sum+=(have[head][cur])/compsz[i];
                cur++;
            }
            ans[j.s]+=((j.f.f/compsz[i])*cur)-sum+t.qry(lb(all(comp),j.f.f%compsz[i])-comp.begin())-cur;
            int val=(j.f.f%compsz[i])-compsz[i]+dist[j.f.s];
            int pos=upper_bound(all(comp),val)-comp.begin()-1;
            if(pos)ans[j.s]+=t.qry(pos);
            val+=compsz[i];
            pos=upper_bound(all(comp),val)-comp.begin()-1;
            if(pos)ans[j.s]+=t.qry(pos)-t.qry(lb(all(comp),j.f.f%compsz[i])-comp.begin());
        }
        t.re();
        qry2.clear();
    }
    for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
}
/*
create  weighted directed graph with cycle on top
a tree will attach to the first node that harvest it with cost of dist
tree will move along the graph. we just need to find how many times a tree passes a given node and time

for qry v,T;
if node v is not in the cycle we can just find the number of tree in the subtree where dist(tree,v)<=T
can use sack on this

else the node v is on the cycle on top
let sz=size of the cycle
we can compute the first node treei will reach in the cycle. let the node be sti
then the time left for tree to move is T-dist(sti,treei)-dist(sti,v) = xi
then we just need to find the sum of floor[xi/sz]?

floor[T-dist/sz]+1 counting the first visit
floor[t-dist/sz]= floor[T/sz]-floor[dist/sz] - (1 if T mod sz< dist mod sz)+1
=floor[T/sz]-floor[dist/sz] + (1 if T mod sz>=dist mod sz)
we can count number of dist mod sz <= T mod sz seperately


1030156923594683
5150784617973418
33230868503053
*/

Compilation message (stderr)

harvest.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
harvest.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void setIO(string name){
      |                       ^
harvest.cpp:44:28: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   44 | int caldist(int from,int go){
      |                            ^
harvest.cpp:49:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   49 | void addedge(int x,int y){
      |                         ^
harvest.cpp:57:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   57 | void getcycle(int cur){
      |                      ^
harvest.cpp: In function 'void getcycle(long long int)':
harvest.cpp:67:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for(int j=1;j<cycle[cnt].size();j++)compsz[cnt]+=caldist(pos[cycle[cnt][j]],pos[cycle[cnt][j-1]])+(k*l);
      |                         ~^~~~~~~~~~~~~~~~~~
harvest.cpp: At global scope:
harvest.cpp:78:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   78 | void getdist(int cur){
      |                     ^
harvest.cpp:95:32: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   95 |     void update(int pos,int val){
      |                                ^
harvest.cpp:100:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  100 |     int qry(int pos){
      |                    ^
harvest.cpp:106:13: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  106 |     void re(){
      |             ^
harvest.cpp:118:27: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  118 | void sack(int cur,int keep){
      |                           ^
harvest.cpp: In function 'void sack(long long int, long long int)':
harvest.cpp:127:9: warning: unused variable 'x' [-Wunused-variable]
  127 |     int x=0;
      |         ^
harvest.cpp: At global scope:
harvest.cpp:143:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  143 | int32_t main(){
      |              ^
harvest.cpp: In function 'int32_t main()':
harvest.cpp:199:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |             while(cur<have[head].size()&&j.f.f>=have[head][cur]){
      |                   ~~~^~~~~~~~~~~~~~~~~~
harvest.cpp: In function 'void setIO(std::string)':
harvest.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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