| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1112115 |
2024-11-13T16:39:41 Z |
lam |
Harvest (JOI20_harvest) |
C++14 |
|
240 ms |
79688 KB |
#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname "temp"
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
ll a[200001],b[200001];
ll n,m,l,c,q;
vector<pair<ll,ll>> adj[500001],adjrev[500001];
ll vis[500001];
ll dist[500001];
ll cnt;
vector<vector<pair<ll,ll>>> compart;
vector<vector<ll>> pref;
vector<ll> len;
ll num[500001];
ll insub[500001];
bool inloop[500001];
ll root;
void dfs(ll u){
if(root) return ;
if(vis[u]){
root=u;
return ;
}
vis[u]=1;
for(auto [v,w]:adj[u]){
dfs(v);
}
}
void dfs1(ll u=root,ll d=0,ll par=0){
vis[u]=1;
num[u]=cnt;
if(u>n){
insub[u]=1;
compart[cnt].push_back({d%len[cnt],d/len[cnt]});
}
for(auto [v,w]:adjrev[u]){
if(v==root) continue;
//cout<<u<<' '<<v<<' '<<root<<ntr;
dfs1(v,d+w,u);
insub[u]+=insub[v];
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//frep;
cin>>n>>m>>l>>c;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
for(int i=1;i<=n;i++){
ll t=((a[i]-c)%l+l)%l;
ll pos=upper_bound(a+1,a+n+1,t)-a-1;
if(pos==0) pos=n;
//if(i==j) continue;
ll v=((a[i]-a[pos])%l+l)%l;
ll cost=(c-v+l-1)/l*l+v;
// cout<<i<<' '<<pos<<' '<<cost<<ntr;
adj[i].push_back({pos,cost});
adjrev[pos].push_back({i,cost});
}
for(int i=1;i<=m;i++){
ll v=upper_bound(a+1,a+n+1,b[i])-a-1;
if(v==0) v=n;
ll cost=((b[i]-a[v])%l+l)%l;
adj[i+n].push_back({v,cost});
adjrev[v].push_back({i+n,cost});
// cout<<i+n<<' '<<v<<' '<<cost<<ntr;
}
compart.push_back({});
pref.push_back({});
len.push_back(0);
for(int i=1;i<=m;i++){
if(vis[i+n]) continue;
root=0,dfs(i+n);
cnt++;
compart.push_back({});
pref.push_back({});
ll p=root;
dist[root]=0;
while(true){
inloop[p]=1;
auto [v,w]=adj[p][0];
if(v==root){
len.push_back(dist[p]+w);
break;
}
dist[v]=dist[p]+w;
p=v;
}
dfs1();
sort(compart[cnt].begin(),compart[cnt].end());
pref[cnt].push_back(compart[cnt][0].second);
for(int i=1;i<compart[cnt].size();i++){
pref[cnt].push_back(pref[cnt].back()+compart[cnt][i].second);
}
}
// for(int i=1;i<=n+m;i++){
// cout<<insub[i]<<' ';
// }
// cout<<ntr;
cin>>q;
for(int i=1;i<=q;i++){
ll u,t;
cin>>u>>t;
t-=dist[u];
if(!inloop[u]){
cout<<insub[u]<<ntr;
continue;
}
else{
ll ans=insub[u]*(dist[u]>0);
ll p=t/len[num[u]];
ll q=t%len[num[u]];
ll lo=0,hi=compart[num[u]].size()-1,pos=-1;
while(lo<=hi){
ll mid=(lo+hi)/2;
if(compart[num[u]][mid].first<=q) pos=mid,lo=mid+1;
else hi=mid-1;
}
ans+=(compart[num[u]].size())*p-pref[num[u]].back();
ans+=pos+1;
cout<<ans<<ntr;
}
}
}
Compilation message
harvest.cpp: In function 'void dfs(long long int)':
harvest.cpp:28:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
28 | for(auto [v,w]:adj[u]){
| ^
harvest.cpp: In function 'void dfs1(long long int, long long int, long long int)':
harvest.cpp:39:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
39 | for(auto [v,w]:adjrev[u]){
| ^
harvest.cpp: In function 'int main()':
harvest.cpp:84:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
84 | auto [v,w]=adj[p][0];
| ^
harvest.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i=1;i<compart[cnt].size();i++){
| ~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
33104 KB |
Output is correct |
| 2 |
Correct |
8 ms |
33872 KB |
Output is correct |
| 3 |
Correct |
8 ms |
33616 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
31824 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
36936 KB |
Output is correct |
| 2 |
Correct |
118 ms |
57416 KB |
Output is correct |
| 3 |
Correct |
107 ms |
59208 KB |
Output is correct |
| 4 |
Correct |
117 ms |
59264 KB |
Output is correct |
| 5 |
Correct |
143 ms |
77896 KB |
Output is correct |
| 6 |
Correct |
127 ms |
77860 KB |
Output is correct |
| 7 |
Correct |
109 ms |
56240 KB |
Output is correct |
| 8 |
Correct |
97 ms |
53936 KB |
Output is correct |
| 9 |
Correct |
159 ms |
79688 KB |
Output is correct |
| 10 |
Correct |
130 ms |
79688 KB |
Output is correct |
| 11 |
Correct |
223 ms |
78664 KB |
Output is correct |
| 12 |
Correct |
240 ms |
78816 KB |
Output is correct |
| 13 |
Correct |
234 ms |
78664 KB |
Output is correct |
| 14 |
Correct |
161 ms |
78676 KB |
Output is correct |
| 15 |
Correct |
144 ms |
70216 KB |
Output is correct |
| 16 |
Correct |
112 ms |
67912 KB |
Output is correct |
| 17 |
Correct |
120 ms |
67768 KB |
Output is correct |
| 18 |
Correct |
66 ms |
45460 KB |
Output is correct |
| 19 |
Correct |
60 ms |
45504 KB |
Output is correct |
| 20 |
Correct |
110 ms |
57428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
33104 KB |
Output is correct |
| 2 |
Correct |
8 ms |
33872 KB |
Output is correct |
| 3 |
Correct |
8 ms |
33616 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
31824 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
