oj.uz

Submission #876194

# Submission time Handle Problem Language Result Execution time Memory
876194 2023-11-21T11:50:04 Z winter0101 Harvest (JOI20_harvest) C++14
100 / 100
 2198 ms 320440 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
const int maxn=2e5+9;
int a[maxn],b[maxn];
struct BIT{
vector<long long>bit;
int n;
void resz(int _n){
n=_n;
bit.clear();
bit.resize(n+1);
for1(i,1,n)bit[i]=0;
}
void add(int pos,long long val){
for(;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
void del(int pos){
for (;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]=0;
}
long long get(int pos){
long long sum=0;
if (pos<0)return 0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
long long get(int l,int r){
if (l>r)return 0;
return get(r)-get(l-1);
}
};
int id[maxn*2];
#define pil pair<int,long long>
vector<pil>g[maxn*2];//edge
int gr[maxn];//group of cycle
int deg[maxn*2];//deg to remove
bool vis[maxn];//travel in cycle
long long dep[maxn];//dep in cycle
int num=0;
vector<int>cc[maxn];//vertice in each cycle
long long len[maxn];
long long dfs(int u){//dfs cycle
gr[u]=num;
cc[num].pb(u);
long long ans=0;
vis[u]=1;
for (auto v:g[u]){
ans+=v.se;
if (!vis[v.fi]){
vis[v.fi]=1;
dep[v.fi]=dep[u]+v.se;
ans+=dfs(v.fi);
}
}
return ans;
}
vector<pil>rg[maxn*2];//reverse edge
long long d[maxn*2];//dep in tree
vector<pil>h[maxn*2];//apple
int in[maxn*2],out[maxn*2];
int rootincyc[maxn*2];
int tme=0;
pil query[maxn];
int n,m;
void redfs(int u,int root){
if (u>n)h[root].pb({u,d[u]});
rootincyc[u]=root;
in[u]=++tme;
for (auto v:rg[u]){
if (deg[v.fi])continue;
d[v.fi]=d[u]+v.se;
redfs(v.fi,root);
}
out[u]=tme;
}
struct line{
int type;//update or answer
int u;//type of apple of vertice
long long val;//time of dep
int idx;
bool operator < (const line &p)const {
if (val==p.val)return type<p.type;
return val<p.val;
}
};
struct queryt2{
int u;
long long k;
int id;
};
vector<line>quest[maxn];
vector<queryt2>quet[maxn];
long long cum(int u,int v){
if (dep[v]>=dep[u])return dep[v]-dep[u];
return len[gr[u]]-(dep[u]-dep[v]);
}
long long answer[maxn];
//solve for cycle
long long du;
long long value[maxn*2];
long long value_mod[maxn*2];
int pos[maxn];
int revpos[maxn*2];
vector<int>arr[maxn*4];
BIT cnt[maxn*4];
BIT st[maxn*4];
int pos_update[maxn*2][20];
int dep_tree[maxn*4];
void build(int id,int l,int r){
arr[id].clear();
arr[id].resize(r-l+1+1),st[id].resz(r-l+1),cnt[id].resz(r-l+1);
int dd=dep_tree[id];
for1(i,1,r-l+1){
arr[id][i]=pos[i+l-1];
}
sort(arr[id].begin()+1,arr[id].begin()+1+r-l+1,[](int i,int j){
return value[i]<value[j];
});
for1(i,1,r-l+1)pos_update[arr[id][i]][dd]=i;
if (l==r)return;
int mid=(l+r)/2;
dep_tree[id*2]=dep_tree[id*2+1]=dep_tree[id]+1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
void update(int id,int l,int r,int u){
if (revpos[u]<l||revpos[u]>r)return;
long long val=(value[u]-value_mod[u])/du;
int dd=dep_tree[id];
st[id].add(pos_update[u][dd],val);
cnt[id].add(pos_update[u][dd],1);
if (l==r)return;
int mid=(l+r)/2;
update(id*2,l,mid,u);
update(id*2+1,mid+1,r,u);
}
long long get(int id,int l,int r,int u,int v,long long val,bool fl){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v){
    int l1=1,r1=r-l+1,as=-1;
    while (l1<=r1){
    int mid=(l1+r1)/2;
    if (value[arr[id][mid]]<=val){
    as=mid;
    l1=mid+1;
    }
    else r1=mid-1;
    }
    if (as==-1)return 0;
    long long nval=((val%du)+du)%du;
    long long mval=(val-nval)/du;
    long long xxx=cnt[id].get(as);
    return xxx*mval-st[id].get(as)+fl*xxx;
}
int mid=(l+r)/2;
return get(id*2,l,mid,u,v,val,fl)+get(id*2+1,mid+1,r,u,v,val,fl);
}
long long l,c;
long long cal(int i,int j){
if (a[j]>=a[i])return a[j]-a[i];
else return l-(a[i]-a[j]);
}
//
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>m>>l>>c;
    for1(i,1,n)cin>>a[i];
    for1(i,1,n)id[i]=i;
    for1(i,n+1,2*n)id[i]=id[i-n];
    for1(i,1,n){
    long long w=(c/l)*l;
    int l1=i+1,r1=i+n,ans=-1;
    while (l1<=r1){
    int mid=(l1+r1)/2;
    if (cal(id[mid],i)>=(c%l)){
    ans=mid;
    l1=mid+1;
    }
    else r1=mid-1;
    }
    if (ans==-1)w+=l,ans=i;
    else w+=cal(id[ans],i);
    g[i].pb({id[ans], w});
    deg[id[ans]]++;
    }
    for1(i,1,m){
    cin>>b[i];
    int l1=1,r1=n,ans=n;
    while (l1<=r1){
    int mid=(l1+r1)/2;
    if (a[mid]<=b[i]){
    ans=mid;
    l1=mid+1;
    }
    else r1=mid-1;
    }
    if (a[ans]<=b[i])g[i+n].pb({ans,b[i]-a[ans]});
    else g[i+n].pb({ans,l-(a[ans]-b[i])});
    }
    queue<int>t;
    for1(i,1,n){
    if (!deg[i]){
    t.push(i);
    }
    }
    while (!t.empty()){
    auto u=t.front();
    t.pop();
    for (auto v:g[u]){
    deg[v.fi]--;
    if (!deg[v.fi]){
    t.push(v.fi);
    }
    }
    }
    vector<long long>cyc;
    num=0;
    for1(i,1,n){
    if (!deg[i]||vis[i])continue;
    //detect cycle
    num++;
    len[num]=dfs(i);
    }
    for1(i,1,n+m){
    for (auto v:g[i]){
    rg[v.fi].pb({i,v.se});
    }
    }
    for1(i,1,n){
    if (deg[i]){
    redfs(i,i);
    }
    }
    int q;
    cin>>q;
    for1(i,1,q){
    cin>>query[i].fi>>query[i].se;
    if (!deg[query[i].fi]){
    quest[rootincyc[query[i].fi]].pb({2,query[i].fi,query[i].se+d[query[i].fi],i});
    }
    else {
    quet[query[i].fi].pb({query[i].fi,query[i].se,i});
    }
    }
    BIT bit;
    bit.resz(n+m);
    for1(i,1,n){
    if (deg[i]){
    vector<line>sol;
    for (auto v:h[i]){
    sol.pb({1,v.fi,v.se,0});
    }
    for (auto v:quest[i]){
    sol.pb(v);
    }
    vector<line>().swap(quest[i]);
    sort(all(sol));
    for (auto v:sol){
    if (v.type==1){
    bit.add(in[v.u],1);
    }
    else {
    answer[v.idx]=bit.get(in[v.u],out[v.u]);
    }
    }
    for (auto v:sol){
    if (v.type==1)bit.del(in[v.u]);
    }
    }
    }
    //d dep in tree
    //dep dep in cycle
    for1(i,1,num){
    du=len[i];
    int nlen=0;
    for(auto u:cc[i]){
    for (auto v:h[u]){
    value[v.fi]=(v.se-dep[u]);
    value_mod[v.fi]=((value[v.fi]%du)+du)%du;
    pos[++nlen]=v.fi;
    }
    }
    if (nlen==0)continue;
    sort(pos+1,pos+nlen+1,[](int x,int y){
    return value_mod[x]<value_mod[y];
    });
    for1(j,1,nlen){
    revpos[pos[j]]=j;
    }
    build(1,1,nlen);
    for(auto u:cc[i]){
    for (auto v:h[u])update(1,1,nlen,v.fi);
    for (auto v:quet[u]){
    int l1=1,r1=nlen,p=0;
    long long val=v.k-dep[v.u];
    long long nval=((val%du)+du)%du;
    while (l1<=r1){
        int mid=(l1+r1)/2;
        if (value_mod[pos[mid]]<=nval){
        p=mid;
        l1=mid+1;
        }
        else r1=mid-1;
    }
    answer[v.id]+=get(1,1,nlen,1,p,val,1)+get(1,1,nlen,p+1,nlen,val,0);
    }
    }
    nlen=0;
    for(auto u:cc[i]){
    for (auto v:h[u]){
    value[v.fi]=(v.se-dep[u]);
    value_mod[v.fi]=((value[v.fi]%du)+du)%du;
    pos[++nlen]=v.fi;
    }
    }
    sort(pos+1,pos+nlen+1,[](int x,int y){
    return value_mod[x]<value_mod[y];
    });
    for1(j,1,nlen){
    revpos[pos[j]]=j;
    }
    build(1,1,nlen);
    reverse(all(cc[i]));
    for(auto u:cc[i]){
    for (auto v:quet[u]){
    int l1=1,r1=nlen,p=0;
    long long val=v.k-dep[v.u]-len[i];
    long long nval=((val%du)+du)%du;
    while (l1<=r1){
        int mid=(l1+r1)/2;
        if (value_mod[pos[mid]]<=nval){
        p=mid;
        l1=mid+1;
        }
        else r1=mid-1;
    }
    answer[v.id]+=get(1,1,nlen,1,p,val,1)+get(1,1,nlen,p+1,nlen,val,0);
    }
    for (auto v:h[u]){
    update(1,1,nlen,v.fi);
    }
    }
    }
    //
    for1(i,1,q){
    if (!deg[query[i].fi])cout<<answer[i]<<'\n';
    else cout<<answer[i]<<'\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 140112 KB Output is correct
2 Correct 31 ms 140880 KB Output is correct
3 Correct 32 ms 141912 KB Output is correct
4 Correct 34 ms 141688 KB Output is correct
5 Correct 33 ms 142012 KB Output is correct
6 Correct 36 ms 141908 KB Output is correct
7 Correct 33 ms 141916 KB Output is correct
8 Correct 38 ms 141508 KB Output is correct
9 Correct 34 ms 141456 KB Output is correct
10 Correct 34 ms 141656 KB Output is correct
11 Correct 34 ms 141660 KB Output is correct
12 Correct 35 ms 141908 KB Output is correct
13 Correct 36 ms 141844 KB Output is correct
14 Correct 35 ms 141404 KB Output is correct
15 Correct 33 ms 141648 KB Output is correct
16 Correct 33 ms 141656 KB Output is correct
17 Correct 34 ms 141644 KB Output is correct
18 Correct 33 ms 141652 KB Output is correct
19 Correct 33 ms 141656 KB Output is correct
20 Correct 34 ms 141652 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 155956 KB Output is correct
2 Correct 163 ms 170476 KB Output is correct
3 Correct 156 ms 179180 KB Output is correct
4 Correct 350 ms 181000 KB Output is correct
5 Correct 169 ms 190020 KB Output is correct
6 Correct 161 ms 190528 KB Output is correct
7 Correct 149 ms 169784 KB Output is correct
8 Correct 155 ms 171108 KB Output is correct
9 Correct 416 ms 189644 KB Output is correct
10 Correct 158 ms 189164 KB Output is correct
11 Correct 455 ms 188620 KB Output is correct
12 Correct 433 ms 188856 KB Output is correct
13 Correct 462 ms 188876 KB Output is correct
14 Correct 180 ms 187072 KB Output is correct
15 Correct 358 ms 182616 KB Output is correct
16 Correct 155 ms 181248 KB Output is correct
17 Correct 155 ms 181428 KB Output is correct
18 Correct 119 ms 160560 KB Output is correct
19 Correct 116 ms 161076 KB Output is correct
20 Correct 149 ms 170592 KB Output is correct

Subtask #3
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 140112 KB Output is correct
2 Correct 31 ms 140880 KB Output is correct
3 Correct 32 ms 141912 KB Output is correct
4 Correct 34 ms 141688 KB Output is correct
5 Correct 33 ms 142012 KB Output is correct
6 Correct 36 ms 141908 KB Output is correct
7 Correct 33 ms 141916 KB Output is correct
8 Correct 38 ms 141508 KB Output is correct
9 Correct 34 ms 141456 KB Output is correct
10 Correct 34 ms 141656 KB Output is correct
11 Correct 34 ms 141660 KB Output is correct
12 Correct 35 ms 141908 KB Output is correct
13 Correct 36 ms 141844 KB Output is correct
14 Correct 35 ms 141404 KB Output is correct
15 Correct 33 ms 141648 KB Output is correct
16 Correct 33 ms 141656 KB Output is correct
17 Correct 34 ms 141644 KB Output is correct
18 Correct 33 ms 141652 KB Output is correct
19 Correct 33 ms 141656 KB Output is correct
20 Correct 34 ms 141652 KB Output is correct
21 Correct 314 ms 155956 KB Output is correct
22 Correct 163 ms 170476 KB Output is correct
23 Correct 156 ms 179180 KB Output is correct
24 Correct 350 ms 181000 KB Output is correct
25 Correct 169 ms 190020 KB Output is correct
26 Correct 161 ms 190528 KB Output is correct
27 Correct 149 ms 169784 KB Output is correct
28 Correct 155 ms 171108 KB Output is correct
29 Correct 416 ms 189644 KB Output is correct
30 Correct 158 ms 189164 KB Output is correct
31 Correct 455 ms 188620 KB Output is correct
32 Correct 433 ms 188856 KB Output is correct
33 Correct 462 ms 188876 KB Output is correct
34 Correct 180 ms 187072 KB Output is correct
35 Correct 358 ms 182616 KB Output is correct
36 Correct 155 ms 181248 KB Output is correct
37 Correct 155 ms 181428 KB Output is correct
38 Correct 119 ms 160560 KB Output is correct
39 Correct 116 ms 161076 KB Output is correct
40 Correct 149 ms 170592 KB Output is correct
41 Correct 915 ms 296000 KB Output is correct
42 Correct 251 ms 207956 KB Output is correct
43 Correct 133 ms 178660 KB Output is correct
44 Correct 1525 ms 307272 KB Output is correct
45 Correct 883 ms 314016 KB Output is correct
46 Correct 906 ms 315480 KB Output is correct
47 Correct 900 ms 316608 KB Output is correct
48 Correct 840 ms 315324 KB Output is correct
49 Correct 823 ms 316256 KB Output is correct
50 Correct 753 ms 295372 KB Output is correct
51 Correct 753 ms 294068 KB Output is correct
52 Correct 1972 ms 318776 KB Output is correct
53 Correct 2198 ms 320440 KB Output is correct
54 Correct 1970 ms 318772 KB Output is correct
55 Correct 1333 ms 317760 KB Output is correct
56 Correct 994 ms 304632 KB Output is correct
57 Correct 999 ms 306080 KB Output is correct
58 Correct 995 ms 306968 KB Output is correct
59 Correct 862 ms 306208 KB Output is correct
60 Correct 842 ms 305608 KB Output is correct
61 Correct 855 ms 306252 KB Output is correct
62 Correct 1741 ms 263104 KB Output is correct
63 Correct 789 ms 286760 KB Output is correct
64 Correct 791 ms 287016 KB Output is correct
65 Correct 788 ms 287676 KB Output is correct
66 Correct 765 ms 286744 KB Output is correct
67 Correct 757 ms 286736 KB Output is correct
68 Correct 761 ms 286184 KB Output is correct
69 Correct 909 ms 297548 KB Output is correct
70 Correct 874 ms 293944 KB Output is correct
71 Correct 965 ms 294424 KB Output is correct
72 Correct 956 ms 294636 KB Output is correct