| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 877548 |
2023-11-23T10:10:42 Z |
mrwang |
Harvest (JOI20_harvest) |
C++14 |
|
139 ms |
110260 KB |
#include<bits/stdc++.h>
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxn=4e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,l,c,a[maxn],b[maxn];
ll d[maxn];
ll dis(ll i,ll j)
{
return (j-i+l)%l;
}
vector<ll>g[maxn];
ll deg[maxn];
bool vis[maxn];
vector<ll>vec[maxn],vv[maxn];
ll nxt[maxn],w[maxn];
bool in[maxn];
void dtmt()
{
queue<int>q;
for(int i=1;i<=n+m;i++)
{
in[i]=true;
if(deg[i]==0) q.push(i);
}
while(!q.empty())
{
ll u=q.front();
in[u]=false;
q.pop();
deg[nxt[u]]--;
if(deg[nxt[u]]==0) q.push(nxt[u]);
}
}
pli e[maxn];
ll tg=0,tin[maxn],tout[maxn],cnt=0,rte[maxn],id[maxn];
ll h[maxn];
vector<ll>app[maxn],pre[maxn];
void dfs(ll u)
{
tin[u]=++tg;
id[u]=cnt;
if(u>n) app[cnt].pb(h[u]);
vis[u]=true;
for(int v:g[u]) h[v]=h[u]+w[v],dfs(v);
tout[u]=tg;
}
ll root[maxn],sum[maxn];
ll bit[maxn];
void update(ll i,ll v)
{
while(i<maxn) bit[i]+=v,i+=i&(-i);
}
ll get(ll i)
{
ll aa=0;
while(i>0) aa+=bit[i],i-=i&(-i);
return aa;
}
ll beg[maxn],ans[maxn];
vector<pli>nen1,nen2;
struct Tq
{
ll v,l,r,id;
bool operator<(const Tq&o)
{
return v<o.v;
}
};
vector<Tq>query1,query2;
void solve()
{
cin >> n >> m >> l >> c;
for(int i=1;i<=n;i++) cin >> a[i],e[i]={a[i],i};
for(int i=1;i<=m;i++) cin >> b[i];
sort(e+1,e+n+1);
for(int i=1;i<=n;i++)
{
ll x=lower_bound(e+1,e+n+1,(pli){(a[i]-(c%l)+l)%l+1,0})-e-1;
ll id;
if(x==0) id=e[n].se;
else id=e[x].se;
nxt[i]=id;
w[i]=dis(a[id],(a[i]-(c%l)+l)%l)+c;
deg[id]++;
}
for(int i=1;i<=m;i++)
{
ll x=lower_bound(e+1,e+n+1,(pli){b[i]+1,0})-e-1;
ll id;
if(x==0) id=e[n].se;
else id=e[x].se;
nxt[i+n]=id;
w[i+n]=dis(a[id],b[i]);
deg[id]++;
}
dtmt();
for(int i=1;i<=n+m;i++) if(in[i]==false) g[nxt[i]].pb(i);
ll sz=0;
for(int i=1;i<=n+m;i++)
{
if(in[i]==true&&vis[i]==false)
{
cnt++;
root[cnt]=i;
vec[cnt].pb(i);
vis[i]=true;
sum[cnt]=w[i];
for(int j=nxt[i];j!=i;j=nxt[j])
{
vis[j]=true;
g[nxt[j]].pb(j);
sum[cnt]+=w[j];
vec[cnt].pb(j);
}
dfs(i);
sort(app[cnt].begin(),app[cnt].end());
beg[i]=sz+1;
for(int j=sz+1;j<=sz+app[cnt].size();j++) nen2.pb({app[cnt][j-sz-1]%sum[cnt],j});
pre[cnt].resize(app[cnt].size());
for(int j=0;j<app[cnt].size();j++)
{
pre[cnt][j]=app[cnt][j]/sum[cnt];
if(j>0) pre[cnt][j]+=pre[cnt][j-1];
}
sz+=app[cnt].size();
ll luu=0;
for(auto zz:vec[cnt]) rte[zz]=luu,luu+=w[zz];
rte[i]=luu;
}
}
for(int i=1;i<=m;i++) nen1.pb({h[i+n],tin[i+n]});
sort(nen1.begin(),nen1.end());
sort(nen2.begin(),nen2.end(),greater<pair<ll,ll>>());
ll q;
cin >> q;
for(int i=1;i<=q;i++)
{
ll v,T;
ans[i]=0;
cin >> v >> T;
query1.pb({T+h[v],tin[v],tout[v],i});
if(in[v])
{
ll u=v;
ll ii=id[u];
ll vc=upper_bound(app[ii].begin(),app[ii].end(),T-rte[u])-app[ii].begin();
if(vc==0) continue;
ll r1=(T-rte[u])/sum[ii];
ll du=(T-rte[u])%sum[ii];
ans[i]+=vc;
ans[i]+=r1*vc-pre[ii][vc-1];
query2.pb({du+1,beg[ii],beg[ii]+vc-1,i});
}
}
sort(query1.begin(),query1.end()),fill(bit,bit+maxn,0);
ll j=0;
for(int i=0;i<query1.size();i++)
{
while(j<nen1.size()&&nen1[j].fi<=query1[i].v) update(nen1[j].se,1),j++;
ans[query1[i].id]+=get(query1[i].r)-get(query1[i].l-1);
}
sort(query2.begin(),query2.end());fill(bit,bit+maxn,0);
j=0;
for(int i=(int)query2.size()-1;i>=0;i--)
{
while(j<nen2.size()&&nen2[j].fi>=query2[i].v) update(nen2[j].se,1),j++;
ans[query2[i].id]-=get(query2[i].r)-get(query2[i].l-1);
}
for(int i=1;i<=q;i++) cout << ans[i]<<'\n';
}
int main()
{
fastio
//freopen("c.INP","r",stdin);
//freopen("c.OUT","w",stdout);
solve();
}
Compilation message
harvest.cpp: In function 'void solve()':
harvest.cpp:125:29: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
125 | for(int j=sz+1;j<=sz+app[cnt].size();j++) nen2.pb({app[cnt][j-sz-1]%sum[cnt],j});
| ~^~~~~~~~~~~~~~~~~~~~
harvest.cpp:127:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int j=0;j<app[cnt].size();j++)
| ~^~~~~~~~~~~~~~~~
harvest.cpp:164:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for(int i=0;i<query1.size();i++)
| ~^~~~~~~~~~~~~~
harvest.cpp:166:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | while(j<nen1.size()&&nen1[j].fi<=query1[i].v) update(nen1[j].se,1),j++;
| ~^~~~~~~~~~~~
harvest.cpp:173:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | while(j<nen2.size()&&nen2[j].fi>=query2[i].v) update(nen2[j].se,1),j++;
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
80752 KB |
Output is correct |
| 2 |
Correct |
17 ms |
81176 KB |
Output is correct |
| 3 |
Correct |
16 ms |
81288 KB |
Output is correct |
| 4 |
Correct |
17 ms |
80988 KB |
Output is correct |
| 5 |
Correct |
16 ms |
81244 KB |
Output is correct |
| 6 |
Correct |
16 ms |
81128 KB |
Output is correct |
| 7 |
Correct |
18 ms |
81244 KB |
Output is correct |
| 8 |
Correct |
16 ms |
80832 KB |
Output is correct |
| 9 |
Correct |
16 ms |
80988 KB |
Output is correct |
| 10 |
Correct |
16 ms |
80988 KB |
Output is correct |
| 11 |
Correct |
16 ms |
80952 KB |
Output is correct |
| 12 |
Correct |
16 ms |
81252 KB |
Output is correct |
| 13 |
Correct |
17 ms |
81244 KB |
Output is correct |
| 14 |
Correct |
17 ms |
81128 KB |
Output is correct |
| 15 |
Correct |
16 ms |
80988 KB |
Output is correct |
| 16 |
Correct |
16 ms |
81144 KB |
Output is correct |
| 17 |
Correct |
18 ms |
80988 KB |
Output is correct |
| 18 |
Correct |
17 ms |
80984 KB |
Output is correct |
| 19 |
Correct |
16 ms |
80988 KB |
Output is correct |
| 20 |
Correct |
16 ms |
80984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
101940 KB |
Output is correct |
| 2 |
Incorrect |
139 ms |
110260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
80752 KB |
Output is correct |
| 2 |
Correct |
17 ms |
81176 KB |
Output is correct |
| 3 |
Correct |
16 ms |
81288 KB |
Output is correct |
| 4 |
Correct |
17 ms |
80988 KB |
Output is correct |
| 5 |
Correct |
16 ms |
81244 KB |
Output is correct |
| 6 |
Correct |
16 ms |
81128 KB |
Output is correct |
| 7 |
Correct |
18 ms |
81244 KB |
Output is correct |
| 8 |
Correct |
16 ms |
80832 KB |
Output is correct |
| 9 |
Correct |
16 ms |
80988 KB |
Output is correct |
| 10 |
Correct |
16 ms |
80988 KB |
Output is correct |
| 11 |
Correct |
16 ms |
80952 KB |
Output is correct |
| 12 |
Correct |
16 ms |
81252 KB |
Output is correct |
| 13 |
Correct |
17 ms |
81244 KB |
Output is correct |
| 14 |
Correct |
17 ms |
81128 KB |
Output is correct |
| 15 |
Correct |
16 ms |
80988 KB |
Output is correct |
| 16 |
Correct |
16 ms |
81144 KB |
Output is correct |
| 17 |
Correct |
18 ms |
80988 KB |
Output is correct |
| 18 |
Correct |
17 ms |
80984 KB |
Output is correct |
| 19 |
Correct |
16 ms |
80988 KB |
Output is correct |
| 20 |
Correct |
16 ms |
80984 KB |
Output is correct |
| 21 |
Correct |
102 ms |
101940 KB |
Output is correct |
| 22 |
Incorrect |
139 ms |
110260 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
