Submission #260689

#	Time	Username	Problem	Language	Result	Execution time	Memory
260689		Kastanda	Harvest (JOI20_harvest)	C++11	0 / 100	536 ms	180848 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;
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, -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, &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;
}

Compilation message (stderr)

harvest.cpp: In function 'int main()':
harvest.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &n, &m, &L, &regenC);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:79:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d", &A[i]);
                 ~~~~~^~~~~~~~~~~~~
harvest.cpp:81:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d", &B[i]);
                 ~~~~~^~~~~~~~~~~~~
harvest.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &q);
         ~~~~~^~~~~~~~~~
harvest.cpp:86:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%lld", &v, &TM[i]);
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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