| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1108265 |
2024-11-03T14:43:04 Z |
8pete8 |
Harvest (JOI20_harvest) |
C++17 |
|
430 ms |
150956 KB |
#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]));
if(c==0){
compsz[cnt]=(k*l);
continue;
}
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(cur<=i&&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));
sort(all(have[head]));
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
1 1 2 559424926
0
1
1
1 759338505386878650
*/
Compilation message
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:71: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]
71 | for(int j=1;j<cycle[cnt].size();j++){
| ~^~~~~~~~~~~~~~~~~~
harvest.cpp: At global scope:
harvest.cpp:84:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
84 | void getdist(int cur){
| ^
harvest.cpp:101:32: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
101 | void update(int pos,int val){
| ^
harvest.cpp:106:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
106 | int qry(int pos){
| ^
harvest.cpp:112:13: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
112 | void re(){
| ^
harvest.cpp:124:27: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
124 | void sack(int cur,int keep){
| ^
harvest.cpp: In function 'void sack(long long int, long long int)':
harvest.cpp:133:9: warning: unused variable 'x' [-Wunused-variable]
133 | int x=0;
| ^
harvest.cpp: At global scope:
harvest.cpp:149:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
149 | int32_t main(){
| ^
harvest.cpp: In function 'int32_t main()':
harvest.cpp:206: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]
206 | 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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
74576 KB |
Output is correct |
| 2 |
Correct |
15 ms |
74876 KB |
Output is correct |
| 3 |
Correct |
16 ms |
75088 KB |
Output is correct |
| 4 |
Correct |
15 ms |
75088 KB |
Output is correct |
| 5 |
Correct |
16 ms |
75344 KB |
Output is correct |
| 6 |
Correct |
15 ms |
75344 KB |
Output is correct |
| 7 |
Correct |
16 ms |
75344 KB |
Output is correct |
| 8 |
Correct |
16 ms |
74832 KB |
Output is correct |
| 9 |
Correct |
14 ms |
74820 KB |
Output is correct |
| 10 |
Correct |
14 ms |
74832 KB |
Output is correct |
| 11 |
Correct |
15 ms |
74832 KB |
Output is correct |
| 12 |
Correct |
17 ms |
75488 KB |
Output is correct |
| 13 |
Correct |
17 ms |
75600 KB |
Output is correct |
| 14 |
Incorrect |
16 ms |
75460 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
175 ms |
94080 KB |
Output is correct |
| 2 |
Correct |
170 ms |
102252 KB |
Output is correct |
| 3 |
Correct |
141 ms |
111544 KB |
Output is correct |
| 4 |
Correct |
222 ms |
123752 KB |
Output is correct |
| 5 |
Correct |
189 ms |
136228 KB |
Output is correct |
| 6 |
Correct |
173 ms |
136120 KB |
Output is correct |
| 7 |
Correct |
140 ms |
98876 KB |
Output is correct |
| 8 |
Correct |
140 ms |
96676 KB |
Output is correct |
| 9 |
Correct |
292 ms |
147632 KB |
Output is correct |
| 10 |
Correct |
275 ms |
148396 KB |
Output is correct |
| 11 |
Correct |
367 ms |
146508 KB |
Output is correct |
| 12 |
Correct |
406 ms |
146608 KB |
Output is correct |
| 13 |
Correct |
430 ms |
146612 KB |
Output is correct |
| 14 |
Correct |
329 ms |
150956 KB |
Output is correct |
| 15 |
Correct |
284 ms |
128956 KB |
Output is correct |
| 16 |
Correct |
171 ms |
119100 KB |
Output is correct |
| 17 |
Correct |
152 ms |
120504 KB |
Output is correct |
| 18 |
Correct |
83 ms |
92496 KB |
Output is correct |
| 19 |
Correct |
90 ms |
92740 KB |
Output is correct |
| 20 |
Incorrect |
137 ms |
105912 KB |
Output isn't correct |
| 21 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
74576 KB |
Output is correct |
| 2 |
Correct |
15 ms |
74876 KB |
Output is correct |
| 3 |
Correct |
16 ms |
75088 KB |
Output is correct |
| 4 |
Correct |
15 ms |
75088 KB |
Output is correct |
| 5 |
Correct |
16 ms |
75344 KB |
Output is correct |
| 6 |
Correct |
15 ms |
75344 KB |
Output is correct |
| 7 |
Correct |
16 ms |
75344 KB |
Output is correct |
| 8 |
Correct |
16 ms |
74832 KB |
Output is correct |
| 9 |
Correct |
14 ms |
74820 KB |
Output is correct |
| 10 |
Correct |
14 ms |
74832 KB |
Output is correct |
| 11 |
Correct |
15 ms |
74832 KB |
Output is correct |
| 12 |
Correct |
17 ms |
75488 KB |
Output is correct |
| 13 |
Correct |
17 ms |
75600 KB |
Output is correct |
| 14 |
Incorrect |
16 ms |
75460 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
