oj.uz

Submission #1108374

# Submission time Handle Problem Language Result Execution time Memory
1108374 2024-11-04T02:12:41 Z 8pete8 Harvest (JOI20_harvest) C++17
100 / 100
 607 ms 168572 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<pii>adj[mxn+10];
void addedge(int x,int y,int z){
    adj[x].pb({y,z});
}
int on[mxn+10],vis[mxn+10],oncycle[mxn+10]; //on cycle
int dist[mxn+10],sz[mxn+10],tin[mxn+10],tout[mxn+10],who[mxn+10],where[mxn+10];
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.f]){
            cnt++;
            cycle[cnt].pb(i.f),oncycle[i.f]=cnt;
            while(st.top()!=i.f)cycle[cnt].pb(st.top()),oncycle[st.top()]=cnt,st.pop();
            reverse(all(cycle[cnt]));
            compsz[cnt]=dist[cur]-dist[i.f]+i.s;
        }
        if(!vis[i.f]){
            dist[i.f]=dist[cur]+i.s;
            getcycle(i.f);
        }
    }
    on[cur]=0;
    if(!st.empty())st.pop();
}

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.f){
        dist[i.f]=dist[cur]+i.s;
        getdist(i.f);
        sz[cur]+=sz[i.f];
    }
    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++;
        pos=min(pos,sz);
        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.f!=cant.s){
        if(sz[i.f]>sz[hvy])hvy=i.f;
    }
    for(auto i:adj[cur])if((cur!=cant.f||i.f!=cant.s)&&i.f!=hvy)sack(i.f,0);
    if(hvy)sack(hvy,1);
    int x=0;
    for(auto i:adj[cur])if(cur!=cant.f||i.f!=cant.s){
        if(i.f!=hvy)for(int j=tin[i.f];j<=tout[i.f];j++)if(who[j]>n)t.update(where[who[j]],1);
        if(have[i.f].size()>have[cur].size())swap(have[cur],have[i.f]);
        for(auto j:have[i.f])have[cur].pb(j);
    }
    if(cur>n)t.update(where[cur],1),have[cur].pb(dist[cur]),sz[cur]=1;
    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,pos[i]-pos[cur-1]+(k*l));
	}
    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,caldist(pos[T],pos[n]));
        else addedge(cur-1,T,caldist(pos[T],pos[cur-1]));
    }
    for(int i=1;i<=cnt;i++){
        cant={cycle[i].back(),cycle[i][0]};
        dist[cycle[i][0]]=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);
        t.re();
    }
    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]);
        sort(all(have[head]));
        cur=0;
        sort(all(comp));
        comp.erase(unique(all(comp)),comp.end());
        t.sz=comp.size();
        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>=0)ans[j.s]+=t.qry(pos);
            val+=compsz[i];
            pos=upper_bound(all(comp),val)-comp.begin()-1;
            if(pos>=0)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
Ti=dist(sti,treei)+dist(sti,v)
then we just need to find the sum of floor[xi/sz]?

floor[T-dist/sz] counting the first visit
floor[t-dist/sz]= floor[T/sz]-floor[dist/sz] - 1 +(1 if T mod sz>= dist mod sz)

group the node at node g
find all node affected when an apple move from sti->g
then add contribution for how many laps can the apple move starting from returning to g
then the apple may still able to move a little which will affect node V iff (T-Ti)%sz>=sz-dist(sti,g)
2 cases
T%sz >= Ti %sz
T%sz-Ti%sz>=sz-dist(sti,g)
T%sz-sz+dist(sti,g)>=Ti%sz
then qry all Ti%sz

if T%sz< Ti%sz
T%sz-Ti%sz+sz>=sz-dist(sti,g)
T%sz+dist(sti,g)>=Ti%sz
qry all Ti%sz in range (T%sz,T%sz+dist(sti,g))

*/

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:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   49 | void addedge(int x,int y,int z){
      |                               ^
harvest.cpp:58:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   58 | void getcycle(int cur){
      |                      ^
harvest.cpp:81:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   81 | void getdist(int cur){
      |                     ^
harvest.cpp:97:32: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   97 |     void update(int pos,int val){
      |                                ^
harvest.cpp:102:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  102 |     int qry(int pos){
      |                    ^
harvest.cpp:109:13: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  109 |     void re(){
      |             ^
harvest.cpp:121:27: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  121 | void sack(int cur,int keep){
      |                           ^
harvest.cpp: In function 'void sack(long long int, long long int)':
harvest.cpp:130:9: warning: unused variable 'x' [-Wunused-variable]
  130 |     int x=0;
      |         ^
harvest.cpp: At global scope:
harvest.cpp:145:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  145 | int32_t main(){
      |              ^
harvest.cpp: In function 'int32_t main()':
harvest.cpp:204: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]
  204 |             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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 74576 KB Output is correct
2 Correct 15 ms 75088 KB Output is correct
3 Correct 17 ms 75344 KB Output is correct
4 Correct 16 ms 75088 KB Output is correct
5 Correct 16 ms 75344 KB Output is correct
6 Correct 16 ms 75344 KB Output is correct
7 Correct 16 ms 75344 KB Output is correct
8 Correct 14 ms 75088 KB Output is correct
9 Correct 15 ms 75088 KB Output is correct
10 Correct 16 ms 75088 KB Output is correct
11 Correct 15 ms 74972 KB Output is correct
12 Correct 18 ms 75528 KB Output is correct
13 Correct 17 ms 75600 KB Output is correct
14 Correct 17 ms 75428 KB Output is correct
15 Correct 15 ms 75344 KB Output is correct
16 Correct 16 ms 75344 KB Output is correct
17 Correct 17 ms 75344 KB Output is correct
18 Correct 16 ms 75088 KB Output is correct
19 Correct 15 ms 75088 KB Output is correct
20 Correct 14 ms 75088 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 94124 KB Output is correct
2 Correct 186 ms 101056 KB Output is correct
3 Correct 169 ms 109240 KB Output is correct
4 Correct 242 ms 121608 KB Output is correct
5 Correct 172 ms 134328 KB Output is correct
6 Correct 190 ms 134364 KB Output is correct
7 Correct 137 ms 98996 KB Output is correct
8 Correct 111 ms 96184 KB Output is correct
9 Correct 288 ms 145624 KB Output is correct
10 Correct 254 ms 146348 KB Output is correct
11 Correct 342 ms 144560 KB Output is correct
12 Correct 410 ms 144460 KB Output is correct
13 Correct 416 ms 144456 KB Output is correct
14 Correct 280 ms 145324 KB Output is correct
15 Correct 251 ms 123412 KB Output is correct
16 Correct 142 ms 116284 KB Output is correct
17 Correct 155 ms 114036 KB Output is correct
18 Correct 118 ms 94780 KB Output is correct
19 Correct 103 ms 94596 KB Output is correct
20 Correct 162 ms 101456 KB Output is correct

Subtask #3
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 74576 KB Output is correct
2 Correct 15 ms 75088 KB Output is correct
3 Correct 17 ms 75344 KB Output is correct
4 Correct 16 ms 75088 KB Output is correct
5 Correct 16 ms 75344 KB Output is correct
6 Correct 16 ms 75344 KB Output is correct
7 Correct 16 ms 75344 KB Output is correct
8 Correct 14 ms 75088 KB Output is correct
9 Correct 15 ms 75088 KB Output is correct
10 Correct 16 ms 75088 KB Output is correct
11 Correct 15 ms 74972 KB Output is correct
12 Correct 18 ms 75528 KB Output is correct
13 Correct 17 ms 75600 KB Output is correct
14 Correct 17 ms 75428 KB Output is correct
15 Correct 15 ms 75344 KB Output is correct
16 Correct 16 ms 75344 KB Output is correct
17 Correct 17 ms 75344 KB Output is correct
18 Correct 16 ms 75088 KB Output is correct
19 Correct 15 ms 75088 KB Output is correct
20 Correct 14 ms 75088 KB Output is correct
21 Correct 162 ms 94124 KB Output is correct
22 Correct 186 ms 101056 KB Output is correct
23 Correct 169 ms 109240 KB Output is correct
24 Correct 242 ms 121608 KB Output is correct
25 Correct 172 ms 134328 KB Output is correct
26 Correct 190 ms 134364 KB Output is correct
27 Correct 137 ms 98996 KB Output is correct
28 Correct 111 ms 96184 KB Output is correct
29 Correct 288 ms 145624 KB Output is correct
30 Correct 254 ms 146348 KB Output is correct
31 Correct 342 ms 144560 KB Output is correct
32 Correct 410 ms 144460 KB Output is correct
33 Correct 416 ms 144456 KB Output is correct
34 Correct 280 ms 145324 KB Output is correct
35 Correct 251 ms 123412 KB Output is correct
36 Correct 142 ms 116284 KB Output is correct
37 Correct 155 ms 114036 KB Output is correct
38 Correct 118 ms 94780 KB Output is correct
39 Correct 103 ms 94596 KB Output is correct
40 Correct 162 ms 101456 KB Output is correct
41 Correct 394 ms 129664 KB Output is correct
42 Correct 243 ms 124784 KB Output is correct
43 Correct 169 ms 119876 KB Output is correct
44 Correct 307 ms 141476 KB Output is correct
45 Correct 344 ms 157360 KB Output is correct
46 Correct 322 ms 155836 KB Output is correct
47 Correct 318 ms 154612 KB Output is correct
48 Correct 287 ms 156744 KB Output is correct
49 Correct 278 ms 157764 KB Output is correct
50 Correct 266 ms 125132 KB Output is correct
51 Correct 281 ms 125232 KB Output is correct
52 Correct 467 ms 166444 KB Output is correct
53 Correct 475 ms 168572 KB Output is correct
54 Correct 479 ms 166652 KB Output is correct
55 Correct 607 ms 166160 KB Output is correct
56 Correct 353 ms 142668 KB Output is correct
57 Correct 321 ms 139192 KB Output is correct
58 Correct 354 ms 143400 KB Output is correct
59 Correct 262 ms 141744 KB Output is correct
60 Correct 279 ms 142264 KB Output is correct
61 Correct 278 ms 142768 KB Output is correct
62 Correct 479 ms 144568 KB Output is correct
63 Correct 196 ms 118340 KB Output is correct
64 Correct 210 ms 118344 KB Output is correct
65 Correct 180 ms 119612 KB Output is correct
66 Correct 180 ms 117092 KB Output is correct
67 Correct 177 ms 118100 KB Output is correct
68 Correct 174 ms 117184 KB Output is correct
69 Correct 306 ms 129876 KB Output is correct
70 Correct 285 ms 129856 KB Output is correct
71 Correct 332 ms 130224 KB Output is correct
72 Correct 316 ms 129740 KB Output is correct