| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1086187 |
2024-09-09T16:58:25 Z |
t9unkubj |
Harvest (JOI20_harvest) |
C++17 |
|
456 ms |
131344 KB |
#ifdef t9unkubj
#include"template.h"
//#include"template_no_debug.h"
#else
#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
#define dbg(...) 199958
using namespace std;
#include<bits/stdc++.h>
using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
template<class T>using vvvc=vvc<vc<T>>;
using vi=vc<int>;
using vvi=vc<vi>;
using vvvi=vc<vvi>;
using vl=vc<ll>;
using vvl=vc<vl>;
using vvvl=vc<vvl>;
template<class T>using smpq=priority_queue<T,vector<T>,greater<T>>;
template<class T>using bipq=priority_queue<T>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define is insert
#define bg begin()
#define ed end()
void scan(int&a) { cin >> a; }
void scan(ll&a) { cin >> a; }
void scan(string&a) { cin >> a; }
void scan(char&a) { cin >> a; }
void scan(uint&a) { cin >> a; }
void scan(ull&a) { cin >> a; }
void scan(bool&a) { cin >> a; }
void scan(ld&a){ cin>> a;}
template<class T> void scan(vector<T>&a) { for(auto&x:a) scan(x); }
void read() {}
template<class Head, class... Tail> void read(Head&head, Tail&... tail) { scan(head); read(tail...); }
#define INT(...) int __VA_ARGS__; read(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; read(__VA_ARGS__);
#define ULL(...) ull __VA_ARGS__; read(__VA_ARGS__);
#define STR(...) string __VA_ARGS__; read(__VA_ARGS__);
#define CHR(...) char __VA_ARGS__; read(__VA_ARGS__);
#define DBL(...) double __VA_ARGS__; read(__VA_ARGS__);
#define LD(...) ld __VA_ARGS__; read(__VA_ARGS__);
#define VC(type, name, ...) vector<type> name(__VA_ARGS__); read(name);
#define VVC(type, name, size, ...) vector<vector<type>> name(size, vector<type>(__VA_ARGS__)); read(name);
void print(int a) { cout << a; }
void print(ll a) { cout << a; }
void print(string a) { cout << a; }
void print(char a) { cout << a; }
void print(uint a) { cout << a; }
void print(bool a) { cout << a; }
void print(ull a) { cout << a; }
void print(double a) { cout << a; }
void print(ld a){ cout<< a; }
template<class T> void print(vector<T>a) { for(int i=0;i<(int)a.size();i++){if(i)cout<<" ";print(a[i]);}cout<<endl;}
void PRT() { cout <<endl; return ; }
template<class T> void PRT(T a) { print(a); cout <<endl; return; }
template<class Head, class... Tail> void PRT(Head head, Tail ... tail) { print(head); cout << " "; PRT(tail...); return; }
template<class T,class F>
bool chmin(T &x, F y){
if(x>y){
x=y;
return true;
}
return false;
}
template<class T, class F>
bool chmax(T &x, F y){
if(x<y){
x=y;
return true;
}
return false;
}
void YesNo(bool b){
cout<<(b?"Yes":"No")<<endl;
}
void Yes(){
cout<<"Yes"<<endl;
}
void No(){
cout<<"No"<<endl;
}
template<class T>
int popcount(T n){
return __builtin_popcountll(n);
}
template<class T>
T sum(vc<T>&a){
return accumulate(all(a),T(0));
}
template<class T>
T max(vc<T>&a){
return *max_element(all(a));
}
template<class T>
T min(vc<T>&a){
return *min_element(all(a));
}
template<class T>
void unique(vc<T>&a){
a.erase(unique(all(a)),a.end());
}
vvi readgraph(int n,int m,int off = -1){
vvi g(n);
rep(i, m){
int u,v;
cin>>u>>v;
u+=off,v+=off;
g[u].push_back(v);
g[v].push_back(u);
}
return g;
}
vvi readtree(int n,int off=-1){
return readgraph(n,n-1,off);
}
template<class T>
vc<T> presum(vc<T> &a){
vc<T> ret(a.size()+1);
rep(i,a.size())ret[i+1]=ret[i]+a[i];
return ret;
}
template<class T, class F>
vc<T> &operator+=(vc<T> &a,F b){
for (auto&v:a)v += b;
return a;
}
template<class T, class F>
vc<T> &operator-=(vc<T>&a,F b){
for (auto&v:a)v-=b;
return a;
}
template<class T, class F>
vc<T> &operator*=(vc<T>&a,F b){
for (auto&v:a)v*=b;
return a;
}
#endif
double pass_time=0;
//k以下のnum
struct range_tree_get_num{
int n;
struct S{
vc<ll>seq;
vc<ll>pre;
void build(const vc<ll>&c){
seq=c;
pre=presum(pre);
}
int size(){
return seq.size();
}
};
vector<S>node;
range_tree_get_num(){}
range_tree_get_num(int N){
int log=0;
while((1<<log)<=N)log++;
n=1<<log;
node=vector<S>(n*2);
}
S merge(S&a,S&b){
S c;
int l=0,r=0;
while(l<(int)a.size()||r<(int)b.size()){
if(l==(int)a.size())c.seq.push_back(b.seq[r++]);
else if(r==(int)b.size())c.seq.push_back(a.seq[l++]);
else if(a.seq[l]<=b.seq[r])c.seq.push_back(a.seq[l++]);
else c.seq.push_back(b.seq[r++]);
}
c.build(c.seq);
return c;
}
void set(int i,vl t){
S c;
c.build({t});
node[i+n]=c;
}
void build(){
for(int i=node.size();i;i--){
int a=i*2,b=i*2+1;
if(b<(int)node.size()){
node[i]=merge(node[a],node[b]);
}
}
}
ll op(ll l,S&c){
return upper_bound(all(c.seq),l)-c.seq.bg;
}
ll prod(int l,int r,ll x){
l+=n,r+=n;
ll res=0;
while(l<r){
if(l&1)res+=op(x,node[l++]);
if(r&1)res+=op(x,node[--r]);
l>>=1,r>>=1;
}
return res;
}
};
struct range_tree_sum{
int n;
struct S{
vc<ll>seq;
vc<ll>pre;
void build(const vc<ll>&c){
seq=c;
pre=presum(seq);
}
int size(){
return seq.size();
}
};
vector<S>node;
range_tree_sum(){}
range_tree_sum(int N){
int log=0;
while((1<<log)<=N)log++;
n=1<<log;
node=vector<S>(n*2);
}
S merge(S&a,S&b){
S c;
int l=0,r=0;
while(l<(int)a.size()||r<(int)b.size()){
if(l==(int)a.size())c.seq.push_back(b.seq[r++]);
else if(r==(int)b.size())c.seq.push_back(a.seq[l++]);
else if(a.seq[l]<=b.seq[r])c.seq.push_back(a.seq[l++]);
else c.seq.push_back(b.seq[r++]);
}
c.build(c.seq);
return c;
}
void set(int i,vl t){
S c;
c.build({t});
node[i+n]=c;
}
void build(){
for(int i=node.size();i;i--){
int a=i*2,b=i*2+1;
if(b<(int)node.size()){
node[i]=merge(node[a],node[b]);
}
}
}
ll op2(ll l,S&c){
return upper_bound(all(c.seq),l)-c.seq.bg;
}
ll counter(int l,int r,ll x){
l+=n,r+=n;
ll res=0;
while(l<r){
if(l&1)res+=op2(x,node[l++]);
if(r&1)res+=op2(x,node[--r]);
l>>=1,r>>=1;
}
return res;
}
ll op(ll l,S&c){
auto itr=upper_bound(all(c.seq),l)-c.seq.bg;
return c.pre[itr];
}
ll prod(int l,int r,ll x){
l+=n,r+=n;
ll res=0;
while(l<r){
if(l&1)res+=op(x,node[l++]);
if(r&1)res+=op(x,node[--r]);
l>>=1,r>>=1;
}
return res;
}
};
template<class T,auto op,int extra>
struct base_dsu{
vector<int>par;
vector<T>data;
base_dsu(int n):par(n,-1){
static_assert(!extra,"e is needed");
}
base_dsu(int n,T e):par(n,-1),data(n,e){}
T& operator[](int i){
static_assert(extra,"No data");
return data[leader(i)];
}
int root(int x){
if(par[x]<0)return x;
else return par[x]=root(par[x]);
}
bool same(int x,int y){
return root(x)==root(y);
}
bool merge(int x,int y){
x=root(x);
y=root(y);
if(x==y)return false;
if(par[x]>par[y])swap(x,y);
par[x]+=par[y];
par[y]=x;
if(extra){
data[x]=op(data[y],data[x]);
}
return true;
}
int size(int x){
return -par[root(x)];
}
int leader(int x){
return root(x);
}
};
int tf323(int a,int b){return a;}
using dsu=base_dsu<int,tf323,0>;
template<class T,auto op>
using extra_dsu=base_dsu<T,op,1>;
int op(int a,int b){
return max(a,b);
}
void solve(){
LL(n,m,l,c);
VC(ll,a,n);
VC(ll,b,m);
a-=1,b-=1;
vc<pll> to(n);
dbg(c%l);
//graphを作る
{
auto A=a;
for(auto&x:a)A.pb(x+l);
rep(i,n){
ll nxt=a[i]-c+l*2e9;
auto itr=upper_bound(all(A),nxt%l)-1-A.bg;
if(itr<0)itr+=n;
itr%=n;
to[i].se=c+(a[itr]<(nxt%l)?(nxt%l)-a[itr]:l+(nxt%l)-a[itr]);
to[i].fi=itr;
assert(to[i].fi>=0);
dbg(to[i]);
}
}
//初期にいる場所とコスト
vvl gs(n);
{
vc<array<ll,3>>events;
rep(i,n){
events.pb({a[i],i,0});
events.pb({a[i]+l,i,0});
}
rep(i,m){
events.pb({b[i],i,1});
events.pb({b[i]+l,i,1});
}
sort(all(events));
ll last=-1;
ll pos=-1;
vi seen(m);
for(auto [x,i,t]:events){
if(t==0){
last=i;
pos=x;
}else{
if(last==-1)continue;
if(seen[i])continue;
seen[i]=1;
gs[last].pb(abs(x-pos));
}
}
}
rep(i,n)dbg(gs[i]);
//rep(i,n)dbg(gs[i]);
///サイクルを作る
vi is_cycle(n);
extra_dsu<int,op> dsu(n,-1);
{
rep(i,n){
if(!dsu.merge(i,to[i].fi)){
int now=i;
while(!is_cycle[now]){
is_cycle[now]=1;
now=to[now].fi;
}
}
}
}
vvc<pii> inv(n);
rep(i,n)inv[to[i].fi].pb({i,to[i].se});
//euler tour
vi in(n,-1);
vi out(n,-1);
int now_time__=0;
function<void(int)>dfs=[&](int now){
in[now]=now_time__++;
for(auto&[x,w]:inv[now]){
if(in[x]==-1){
dfs(x);
}
}
out[now]=now_time__;
};
rep(i,n){
if(in[i]==-1&&is_cycle[i])dfs(i);
}
//パスを考える
dbg(222222222222);
rep(i,n){
if(is_cycle[i]){
dsu[i]=i;
}
}
vl md_to_cycle(n,1e18);
vl from(n,-1);
queue<array<ll,3>>que;
rep(i,n){
if(is_cycle[i]){
md_to_cycle[i]=0;
que.push({0,i,i});
from[i]=i;
}
}
while(que.size()){
auto [p,q,r]=que.front();que.pop();
for(auto&[x,w]:inv[q]){
if(chmin(md_to_cycle[x],p+w)){
from[x]=r;
que.push({md_to_cycle[x],x,r});
}
}
}
dbg(md_to_cycle);
vvl cycle_vs(n);//サイクル上のここに来るまでのコスト
rep(i,n){
for(auto&x:gs[i]){
dbg(i,x);
cycle_vs[from[i]].pb(x+md_to_cycle[i]);
}
}
//全部leaderにそろえる
vl md_to_leader(n,1e18);
rep(i,n){
if(dsu[i]==i){
md_to_leader[i]=0;
que.push({0,i,i});
}
}
while(que.size()){
auto [p,q,hogehoge]=que.front();que.pop();
for(auto&[x,w]:inv[q]){
if(chmin(md_to_leader[x],p+w)){
que.push({md_to_leader[x],x,hogehoge});
}
}
}
//leaderから出発したき
vl md_from_leader(n,1e18);
rep(i,n){
if(dsu[i]==i){
md_from_leader[i]=0;
que.push({0,i,i});
}
}
while(que.size()){
auto [p,q,hogehoge]=que.front();que.pop();
{
ll x=to[q].fi,w=to[q].se;
if(chmin(md_from_leader[x],p+w)){
que.push({md_from_leader[x],x,hogehoge});
}
}
}
dbg(md_from_leader);
//1サイクル当たり
vl cycle_w(n,c);
rep(i,n){
if(is_cycle[i]){
ll x=to[i].fi,y=to[i].se;
chmax(cycle_w[dsu[i]],md_from_leader[i]+y);
}
}
dbg(md_to_leader);
//まとめる
vvl vs_leader(n);
rep(i,n){
if(is_cycle[i]){
for(auto&x:cycle_vs[i]){
vs_leader[dsu[i]].pb(x+md_to_leader[i]);
}
}
}
dbg(cycle_w);
rep(i,n){
sort(all(vs_leader[i]),[&](auto a,auto b){
return a%cycle_w[i]<b%cycle_w[i];
});
}
dbg(333);
//部分木に対してクエリ，eulerツアー順，md_to_cycle[i]を足す
range_tree_get_num rt(n);
rep(i,n){
gs[i]+=md_to_cycle[i];
if(gs[i].size())rt.set(in[i],gs[i]);
}
dbg(333);
rt.build();
using R=range_tree_sum;
vc<R>leader_rt_down(n);
vc<R>leader_rt_up(n);
rep(i,n){
if(dsu[i]!=i)continue;
leader_rt_down[i]=leader_rt_up[i]=R(vs_leader[i].size());
rep(j,vs_leader[i].size())leader_rt_down[i].set(j,{vs_leader[i][j]/cycle_w[dsu[i]]}),leader_rt_up[i].set(j,{(vs_leader[i][j]+cycle_w[dsu[i]]-1)/cycle_w[dsu[i]]});
leader_rt_down[i].build();
leader_rt_up[i].build();
}
//cycleをseg木に並べる
vi in_cycle(n,-1);
vi left(n,1e9);
int now_time=0;
dbg(333);
rep(i,n){
if(dsu[i]==i){
int now=i;
do{
in_cycle[now]=now_time++;
chmin(left[i],now_time);
now=to[now].fi;
}while(now!=i);
}
}
range_tree_get_num rt3(n);
rep(i,n){
if(is_cycle[i]){
dbg(cycle_vs[i]);
cycle_vs[i]+=md_to_leader[i];
if(cycle_vs[i].size())rt3.set(in_cycle[i],cycle_vs[i]);
cycle_vs[i]+=-md_to_leader[i];
}
}
rt3.build();
INT(q);
dbg(in,out);
while(q--){
LL(x,t);
--x;
if(is_cycle[x]){
ll r=dsu[x];
ll L=cycle_w[r];
ll ans=0;
//[0,ac]がt未満のあまり
t-=md_from_leader[x];
ll ac=-1,wa=vs_leader[r].size();
while(wa-ac>1){
ll wj=ac+wa>>1;
if(vs_leader[r][wj]%L<=t%L){
ac=wj;
}else{
wa=wj;
}
}
//t/L以下のsum,そのままできる
//ans+=(ac+1)*(t/L+1)-(leader_rt_down[r].prod(0,ac+1,t/L));
ans+=leader_rt_down[r].counter(0,ac+1,t/L)*(t/L+1)-(leader_rt_down[r].prod(0,ac+1,t/L));
//[ac+1,をみる
int sz=vs_leader[r].size();
//ans+=(sz-(ac+1)+1)*((t+L-1)/L+1)-(leader_rt_up[r].prod(ac+1,sz,(t+L-1)/L));
ans+=leader_rt_up[r].counter(ac+1,sz,t/L)*(t/L+1)-(leader_rt_up[r].prod(ac+1,sz,t/L));
//ans+=leader_rt_up[r].counter(ac+1,sz,(t+L-1)/L)*((t+L-1)/L+1)-(leader_rt_up[r].prod(ac+1,sz,(t+L-1)/L));
t+=md_from_leader[x];
//こっちに入っているやつのうちvalidなもの
ans+=rt3.prod(left[r],in_cycle[x]+1,t+md_to_leader[x]);
//dbg(left[r],in_cycle[x]+1,x,rt3.prod(left[r],in_cycle[x]+1,t+md_to_leader[x]));
PRT(ans);
}else{
int l=in[x],r=out[x];
auto res=rt.prod(l,r,md_to_cycle[x]+t);
PRT(res);
}
}
}
signed main(){
#ifdef t9unkubj
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin.tie(0)->sync_with_stdio(0);
pass_time=clock();
int t=1;
//cin>>t;
while(t--)solve();
pass_time=clock()-pass_time;
dbg(pass_time/CLOCKS_PER_SEC);
}
Compilation message
harvest.cpp: In function 'void solve()':
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:352:5: note: in expansion of macro 'dbg'
352 | dbg(c%l);
| ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:365:13: note: in expansion of macro 'dbg'
365 | dbg(to[i]);
| ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:396:13: note: in expansion of macro 'dbg'
396 | rep(i,n)dbg(gs[i]);
| ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:432:5: note: in expansion of macro 'dbg'
432 | dbg(222222222222);
| ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:457:5: note: in expansion of macro 'dbg'
457 | dbg(md_to_cycle);
| ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:461:13: note: in expansion of macro 'dbg'
461 | dbg(i,x);
| ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:499:5: note: in expansion of macro 'dbg'
499 | dbg(md_from_leader);
| ^~~
harvest.cpp:504:16: warning: unused variable 'x' [-Wunused-variable]
504 | ll x=to[i].fi,y=to[i].se;
| ^
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:508:5: note: in expansion of macro 'dbg'
508 | dbg(md_to_leader);
| ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:519:5: note: in expansion of macro 'dbg'
519 | dbg(cycle_w);
| ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:525:6: note: in expansion of macro 'dbg'
525 | dbg(333);
| ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:532:5: note: in expansion of macro 'dbg'
532 | dbg(333);
| ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:551:5: note: in expansion of macro 'dbg'
551 | dbg(333);
| ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:566:13: note: in expansion of macro 'dbg'
566 | dbg(cycle_vs[i]);
| ^~~
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:574:5: note: in expansion of macro 'dbg'
574 | dbg(in,out);
| ^~~
harvest.cpp:586:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
586 | ll wj=ac+wa>>1;
| ~~^~~
harvest.cpp: In function 'int main()':
harvest.cpp:7:18: warning: statement has no effect [-Wunused-value]
7 | #define dbg(...) 199958
| ^~~~~~
harvest.cpp:625:5: note: in expansion of macro 'dbg'
625 | dbg(pass_time/CLOCKS_PER_SEC);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
352 ms |
6520 KB |
Output is correct |
| 2 |
Incorrect |
456 ms |
131344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
