Submission #262366

#	Time	Username	Problem	Language	Result	Execution time	Memory
262366		Kastanda	Harvest (JOI20_harvest)	C++11	100 / 100	2052 ms	252280 KiB

harvest

// M
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template < typename T >
using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
typedef long long ll;
const int N = 200195;
int n, m, q, L, regenC, FNL, ts, A[N], B[N], M[N], Nxt[N];
ll T[N], RS[N], Lnxt[N], lz[N], D[N], F[N];
vector < int > Q[N], In[N], V[N];
vector < pair < ll , int > > VST[N];
ordered_set < pair < ll , int > > ST[N], TS[N];
void DFS(int v)
{
        M[v] = 1;
        for (int u : In[v])
        {
                if (!M[u])
                        DFS(u);
                if (u == v)
                        continue;
                lz[u] += Lnxt[u];
                if (ST[v].size() < ST[u].size())
                        ST[v].swap(ST[u]), swap(lz[v], lz[u]);
                for (auto a : ST[u])
                        ST[v].insert(make_pair(a.first + lz[u] - lz[v], a.second));
                ST[u].clear(); lz[u] = 0;
        }
        for (auto a : VST[v])
                ST[v].insert(make_pair(a.first - lz[v], a.second));
        for (int i : Q[v])
                RS[i] += ST[v].order_of_key({T[i] - lz[v], N});
}
inline void AddFen(int i, ll val)
{
        for (i ++; i < FNL; i += i & - i)
                F[i] += val;
}
inline ll GetFen(int i)
{
        ll rt = 0;
        for (i ++; i; i -= i & - i)
                rt += F[i];
        return rt;
}
inline void AddRem(int i, ll val)
{
        for (i ++; i < FNL; i += i & - i)
                TS[i].insert({val, ts ++});
}
inline ll GetRem(int i, ll le, ll ri)
{
        ll rt = 0;
        for (i ++; i; i -= i & - i)
                rt += TS[i].order_of_key({ri, -1}) - TS[i].order_of_key({le, -1});
        return rt;
}
int main()
{
        scanf("%d%d%d%d", &n, &m, &L, &regenC);
        for (int i = 1; i <= n; i ++)
                scanf("%d", &A[i]);
        for (int i = 1; i <= m; i ++)
                scanf("%d", &B[i]);
        scanf("%d", &q);
        for (int i = 1; i <= q; i ++)
        {
                int v;
                scanf("%d%lld", &v, &T[i]);
                Q[v].push_back(i);
        }

        // Building function graph ...
        for (int i = 1; i <= n; i ++)
        {
                ll c = regenC / L;
                ll r = regenC % L;
                Lnxt[i] += (ll)c * L;
                if (A[1] <= A[i] - r)
                        Nxt[i] = upper_bound(A + 1, A + n + 1, A[i] - r) - A - 1, Lnxt[i] += A[i] - A[Nxt[i]];
                else
                        Nxt[i] = upper_bound(A + 1, A + n + 1, A[i] - r + L) - A - 1, Lnxt[i] += L + A[i] - A[Nxt[i]];
        }
        for (int i = 1, ptr = 1; i <= m; i ++)
        {
                if (B[i] < A[1])
                        VST[n].push_back({B[i] + L - A[n], i});
                else
                {
                        while (ptr < n && A[ptr + 1] <= B[i])
                                ptr ++;
                        VST[ptr].push_back({B[i] - A[ptr], i});
                }
        }
        for (int i = 1; i <= n; i ++)
                In[Nxt[i]].push_back(i);
        for (int i = 1; i <= n; i ++)
                if (!M[i])
                        DFS(i);
        for (int i = 1; i <= n; i ++)
                if (ST[i].size()) // Head of a circle
                {
                        vector < int > C = {i};
                        int nw = Nxt[i];
                        while (nw != i)
                                C.push_back(nw), nw = Nxt[nw];
                        int k = (int)C.size();
                        C.push_back(i);
                        vector < ll > vec;
                        for (auto a : ST[i])
                                vec.push_back(a.first + lz[i]);
                        sort(vec.begin(), vec.end()); // Redundant
                        FNL = max((int)vec.size(), k) + 10;
                        D[0] = 0;
                        for (int j = 1; j <= k; j ++)
                                D[j] = D[j - 1] + Lnxt[C[j - 1]];
                        ll CL = D[k];
                        for (int j = 0; j < (int)vec.size(); j ++)
                        {
                                AddFen(j, vec[j] / CL);
                                AddRem(j, vec[j] % CL);
                                int lb = lower_bound(D + 1, D + k + 1, CL - vec[j] % CL) - D;
                                assert(lb <= k);
                                V[lb].push_back(j);
                        }
                        for (int j = 1; j <= k; j ++)
                        {
                                for (int id : V[j])
                                        AddFen(id, 1LL);

                                for (int id : Q[C[j]])
                                {
                                        int lb = upper_bound(vec.begin(), vec.end(), T[id] - D[j]) - vec.begin();
                                        RS[id] += (T[id] / CL) * (ll)lb;
                                        RS[id] -= GetFen(lb - 1);

                                        ll le = 0, ri = T[id] % CL;
                                        le = (le - D[j] % CL + CL) % CL;
                                        ri = (ri - D[j] % CL + CL) % CL;
                                        ri ++;

                                        if (le < ri)
                                                RS[id] += GetRem(lb - 1, le, ri);
                                        else
                                                RS[id] += GetRem(lb - 1, 0, ri) + GetRem(lb - 1, le, CL);
                                }
                        }

                        for (int j = 0; j <= FNL; j ++)
                        {
                                ts = 0;
                                F[j] = D[j] = 0;
                                TS[j].clear();
                                V[j].clear();
                        }
                }
        for (int i = 1; i <= q; i ++)
                printf("%lld\n", RS[i]);
        return 0;
}

Compilation message (stderr)

harvest.cpp: In function 'int main()':
harvest.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |         scanf("%d%d%d%d", &n, &m, &L, &regenC);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:65:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |                 scanf("%d", &A[i]);
      |                 ~~~~~^~~~~~~~~~~~~
harvest.cpp:67:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |                 scanf("%d", &B[i]);
      |                 ~~~~~^~~~~~~~~~~~~
harvest.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |         scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
harvest.cpp:72:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |                 scanf("%d%lld", &v, &T[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 75 / 75