| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1068594 |
2024-08-21T10:51:20 Z |
AdamGS |
Harvest (JOI20_harvest) |
C++17 |
|
122 ms |
74104 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=4e5+7;
vector<ll>S[LIM];
vector<pair<ll,ll>>V[LIM], pyt[LIM], pyt2[LIM];
vector<pair<pair<ll,ll>,ll>>M;
ll A[LIM], B[LIM], n, m, L, C;
pair<ll,ll>T[2*LIM];
ll nxt[LIM], kraw[LIM], odw[LIM], odl[LIM], cykl[LIM], pre[LIM], post[LIM], wynik[LIM], lpre=-1;
ll korzen[LIM], tr[4*LIM], suma[LIM], N=1;
void upd(int v, ll x) {
v+=N;
while(v) {
tr[v]+=x;
v/=2;
}
}
ll cnt(int l, int r) {
if(l>r) return 0;
l+=N; r+=N;
ll ans=tr[l];
if(l!=r) ans+=tr[r];
while(l/2!=r/2) {
if(l%2==0) ans+=tr[l+1];
if(r%2==1) ans+=tr[r-1];
l/=2; r/=2;
}
return ans;
}
void DFS(int x) {
pre[x]=++lpre;
for(auto i : V[x]) {
odl[i.st]=odl[x]+i.nd;
korzen[i.st]=korzen[x];
DFS(i.st);
}
post[x]=lpre;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> L >> C;
while(N<n) N*=2;
rep(i, n) cin >> A[i];
rep(i, m) cin >> B[i];
ll l=n-1, d=0;
for(int i=n-1; i>=0; --i) if(n>1) {
while(d<C%L) {
d+=(A[l]-A[(l-1+n)%n]+L)%L;
l=(l-1+n)%n;
}
nxt[i]=l;
kraw[i]=d;
if(d<C) kraw[i]+=((C-d+L-1)/L)*L;
d-=(A[i]-A[(i-1+n)%n]+L)%L;
}
if(n==1) {
kraw[0]=(C+L-1)/L;
}
rep(i, n) korzen[i]=-1;
rep(i, n) if(!odw[i]) {
int p=i;
while(!odw[p]) {
odw[p]=i+1;
p=nxt[p];
}
if(odw[p]==i+1) {
korzen[p]=p;
int q=p;
do {
cykl[q]=1;
q=nxt[q];
} while(q!=p);
}
}
rep(i, n) if(korzen[i]!=i) V[nxt[i]].pb({i, kraw[i]});
rep(i, n) if(korzen[i]==i) DFS(i);
int q;
cin >> q;
rep(i, q) {
ll v, t;
cin >> v >> t; --v;
pyt[v].pb({t, i});
}
rep(i, n) T[i]={A[i], i};
rep(i, m) T[n+i]={B[i], n+i};
sort(T, T+n+m);
int lst=0;
rep(i, n+m) if(T[i].nd<n) lst=T[i].nd;
rep(i, n+m) {
if(T[i].nd<n) lst=T[i].nd;
else {
S[korzen[lst]].pb(odl[lst]+(T[i].st-A[lst]+L)%L);
M.pb({{odl[lst]+(T[i].st-A[lst]+L)%L, -1}, lst});
}
}
rep(i, n) if(korzen[i]!=i) {
for(auto j : pyt[i]) M.pb({{odl[i]+j.st, j.nd}, i});
}
sort(all(M));
for(auto i : M) {
if(i.st.nd==-1) {
upd(pre[i.nd], 1);
} else {
wynik[i.st.nd]=cnt(pre[i.nd], post[i.nd]);
}
}
rep(i, n) if(cykl[i]) suma[korzen[i]]+=kraw[i];
rep(i, n) if(cykl[i]) {
ll m=suma[korzen[i]], d=(m-odl[i])%m;
for(auto j : pyt[i]) {
pyt2[korzen[i]].pb({j.st-d, j.nd});
}
}
rep(i, n) if(korzen[i]==i && S[i].size()) {
ll m=suma[i];
vector<ll>K;
for(auto j : S[i]) K.pb(j%m);
sort(all(K));
sort(all(S[i]));
sort(all(pyt2[i]));
l=0;
ll ilek=0, sumk=0;
N=1;
while(N<K.size()) N*=2;
rep(j, 2*N) tr[j]=0;
for(auto j : pyt2[i]) {
while(l<S[i].size() && S[i][l]<=j.st) {
++ilek;
sumk+=S[i][l]/m;
ll po=0, ko=K.size()-1;
while(po<ko) {
ll sr=(po+ko+1)/2;
if(K[sr]>S[i][l]%m) ko=sr-1; else po=sr;
}
upd(po, 1);
++l;
}
ll po=0, ko=K.size()-1;
while(po<ko) {
ll sr=(po+ko+1)/2;
if(K[sr]>j.st%m) ko=sr-1; else po=sr;
}
if(K[po]<=j.st%m) wynik[j.nd]+=cnt(0, po);
wynik[j.nd]+=ilek*(j.st/m);
wynik[j.nd]-=sumk;
}
}
rep(i, q) cout << wynik[i] << '\n';
}
Compilation message
harvest.cpp: In function 'int main()':
harvest.cpp:130:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | while(N<K.size()) N*=2;
| ~^~~~~~~~~
harvest.cpp:133:11: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | while(l<S[i].size() && S[i][l]<=j.st) {
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
57432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
74104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
57432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
