| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 260688 | Kastanda | Harvest (JOI20_harvest) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// M
#include<bits/stdc++.h>
#define int long long
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
template < typename T >
using ordered_set = tree < T , null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
const int N = 200095;
int n, m, q, L, regenC, A[N], B[N];
int cp, Nxt[N], Lnxt[N], CP[N], M[N], is[N];
ll lz[N], D[N * 2];
vector < int > Q[N], Cyc[N], In[N], VF[N];
ordered_set < pair < ll , int > > ST[N];
vector < ll > U, V1[N], V2[N];
ll TM[N], RS[N];
void DFS(int v)
{
M[v] = 1;
for (int p : In[v])
if (!is[p])
{
if (!M[p])
DFS(p);
lz[p] += Lnxt[p];
if (ST[v].size() < ST[p].size())
ST[v].swap(ST[p]), swap(lz[v], lz[p]);
for (auto a : ST[p])
ST[v].insert(make_pair(a.first + lz[p] - lz[v], a.second));
ST[p].clear();
lz[p] = 0;
}
if (!is[v])
{
for (int i : Q[v])
RS[i] = ST[v].order_of_key(make_pair(TM[i], N));//, printf("%lld :::: %d\n", i, RS[i]);
return ;
}
}
int tttm = 0;
ll SM[N];
ordered_set < pair < ll , int > > SS[N];
inline void AddSeg(int i, ll a, ll b)
{
assert(b >= 0);
for (i ++; i < (int)U.size() + 5; i += i & - i)
SM[i] += a, SS[i].insert({b, tttm ++});
}
inline void AddSegSM(int i, ll a)
{
for (i ++; i < (int)U.size() + 5; i += i & - i)
SM[i] += a;
}
inline void DelSeg(int i, ll a, ll b)
{
assert(b >= 0);
for (i ++; i < (int)U.size() + 5; i += i & - i)
SM[i] -= a, SS[i].erase(SS[i].lower_bound({b, -1}));
}
inline ll GetSM(int r)
{
ll rt = 0;
for (r ++; r; r -= r & - r)
rt += SM[r];
return rt;
}
inline ll GetVC(int r, ll le, ll ri)
{
ll rt = 0;
for (r ++; r; r -= r & - r)
rt += SS[r].order_of_key({ri, -1}) - SS[r].order_of_key({le, tttm + 10});
return rt;
}
int main()
{
scanf("%lld%lld%lld%lld", &n, &m, &L, ®enC);
for (int i = 1; i <= n; i ++)
scanf("%lld", &A[i]);
for (int i = 1; i <= m; i ++)
scanf("%lld", &B[i]);
scanf("%lld", &q);
for (int i = 1; i <= q; i ++)
{
int v;
scanf("%lld%lld", &v, &TM[i]);
Q[v].push_back(i);
}
// Building the function graph ...
for (int i = 1; i <= n; i ++)
{
ll c = regenC / L;
ll r = regenC % L;
Lnxt[i] = c * L;
if (A[1] <= A[i] - r)
{
int lb = upper_bound(A + 1, A + n + 1, A[i] - r) - A - 1;
Nxt[i] = lb;
Lnxt[i] += A[i] - A[Nxt[i]];
}
else
{
int lb = upper_bound(A + 1, A + n + 1, A[i] - r + L) - A - 1;
Nxt[i] = lb;
Lnxt[i] += A[i] - A[Nxt[i]] + L;
}
//printf("%d : %d , %d\n", i, Nxt[i], Lnxt[i]);
}
for (int i = 1; i <= n; i ++)
if (!CP[i])
{
cp ++;
int nw = i;
while (!CP[nw])
{
CP[nw] = cp;
M[nw] = i;
nw = Nxt[nw];
}
if (M[nw] == i)
{
// nw is part of the cycle
int v = Nxt[nw];
Cyc[cp].push_back(nw);
while (nw != v)
Cyc[cp].push_back(v), v = Nxt[v];
}
else
{
int cl = CP[nw];
cp --;
nw = i;
while (M[nw] == i)
CP[nw] = cl, nw = Nxt[nw];
}
}
for (int i = 1; i <= cp; i ++)
for (int a : Cyc[i])
is[a] = 1;
for (int i = 1; i <= n; i ++)
In[Nxt[i]].push_back(i);
// Done ?
// Now adding queries
int last = n;
for (int i = 1; i <= m; i ++)
{
if (last == n && B[i] < A[n] && B[i] >= A[1])
last = 1;
while (last < n && B[i] >= A[last + 1])
last ++;
int a = B[i] - A[last];
if (a < 0) a += L;
ST[last].insert({a, i});
}
// Added
/*for (int i = 1; i <= n; i ++)
printf("%d ", CP[i]);
printf("\n");
fflush(stdout);
for (int a : Cyc[1])
printf("%d ", a);
printf("\n");*/
// Now to run a dfs of some sort?
memset(M, 0, sizeof(M));
for (int i = 1; i <= n; i ++)
if (!M[i])
DFS(i);
for (int i = 1; i <= cp; i ++)
{
// Resetting
U.clear();
for (int j = 0; j <= (int)Cyc[i].size() + 1; j ++)
V1[j].clear(), V2[j].clear(), VF[j].clear();
ll cycL = 0;
for (int v : Cyc[i])
cycL += Lnxt[v];
ll curd = 0;
for (int j = (int)Cyc[i].size() - 1; j; j --)
{
curd += Lnxt[Cyc[i][j]];
for (auto a : ST[Cyc[i][j]])
{
U.push_back(a.first + curd + lz[Cyc[i][j]]);
V1[j].push_back(a.first + curd + lz[Cyc[i][j]]);
}
}
curd = 0;
for (int j = 0; j < (int)Cyc[i].size(); j ++)
{
for (auto a : ST[Cyc[i][j]])
{
U.push_back(a.first + curd + lz[Cyc[i][j]]);
V2[j].push_back(a.first + curd + lz[Cyc[i][j]]);
}
curd -= Lnxt[Cyc[i][j]];
}
sort(U.begin(), U.end());
U.resize(unique(U.begin(), U.end()) - U.begin());
for (int j = 0; j < (int)U.size() + 20; j ++)
SS[j].clear(), SM[j] = 0;
/*for (int v : Cyc[i])
{
printf("%d : ", v);
for (auto a : ST[v])
printf("%lld ", a.first + lz[v]);
printf("\n");
}*/
int k = (int)Cyc[i].size();
for (int j = 0; j <= k + k; j ++)
D[j] += Lnxt[Cyc[i][j]], D[j + 1] += D[j];
for (int j = 1; j < k; j ++)
{
for (ll a : V1[j])
{
int lb = lower_bound(U.begin(), U.end(), a) - U.begin();
int wt = lower_bound(D, D + k + k, cycL - a % cycL) - D + 1;
//printf("Adding : %lld\n", a);
AddSeg(lb, a / cycL, a % cycL);
if (wt < j)
VF[wt].push_back(lb);
}
}
ll curlz = 0;
for (int j = 0; j < k; j ++)
{
for (int lb : VF[j])
AddSegSM(lb, 1);//, printf("%d =====\n", lb);
for (ll a : V1[j])
{
int lb = lower_bound(U.begin(), U.end(), a) - U.begin();
int wt = lower_bound(D, D + k + k, cycL - a % cycL) - D + 1;
//printf("Delling : %lld\n", a);
DelSeg(lb, a / cycL, a % cycL);
if (wt < j)
AddSegSM(lb, -1);
}
for (ll a : V2[j])
{
int lb = lower_bound(U.begin(), U.end(), a) - U.begin();
ll ddd = j ? D[j - 1] : 0LL;
int wt = lower_bound(D + j, D + k + k, cycL - ((a + curlz) % cycL + cycL) % cycL + ddd) - D + 1;
//printf("Adding : %lld\n", a);
assert(a + curlz >= 0);
AddSeg(lb, (a + curlz) / cycL, (a % cycL + cycL) % cycL);
if (wt < k)
VF[wt].push_back(lb);
}
for (int qid : Q[Cyc[i][j]])
{
//printf("Answering ..\n");
//printf("lazy : %lld\n", curlz);
int lb = upper_bound(U.begin(), U.end(), TM[qid] - curlz) - U.begin();
int cnt = GetVC(lb, (ll)(-2e18), (ll)(2e18));
//printf("====: %d , %d\n", lb, cnt);
RS[qid] -= GetSM(lb);
//printf("# %lld ::\n", RS[qid]);
//RS[qid] += (ll)cnt;
RS[qid] += ((TM[qid] + 1) / cycL) * cnt;
//printf("# %lld ::\n", RS[qid]);
ll rle = 0, rri = (TM[qid] + 1) % cycL;
if (rle == rri)
continue;
rle = (rle - curlz % cycL + cycL) % cycL;
rri = (rri - curlz % cycL + cycL) % cycL;
if (rle < rri)
RS[qid] += GetVC(lb, rle, rri);
else if (rri < rle)
RS[qid] += cnt - GetVC(lb, rri, rle);
else
assert(0);
/*printf("%lld =====\n", RS[qid]);
return 0;*/
}
curlz += Lnxt[Cyc[i][j]];
}
}
for (int i = 1; i <= q; i ++)
printf("%lld\n", RS[i]);
return 0;
}