Submission #398188

#	Time	Username	Problem	Language	Result	Execution time	Memory
398188		duality	Harvest (JOI20_harvest)	C++11	100 / 100	2211 ms	461544 KiB

harvest

#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#pragma GCC optimize("Ofast")

int A[200000],B[200000];
vector<pair<LLI,int> > queries[200000];
LLI ans[200000];
int n[200000];
LLI t[200000];
int in[200000];
vi adjList[200000];
queue<int> QQ;
ordered_set<pair<LLI,int> > S[200000];
LLI add[200000];
int doDFS(int u) {
    int i;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        doDFS(v),add[v] += t[v];
        if (S[v].size() > S[u].size()) S[u].swap(S[v]),swap(add[u],add[v]);
        for (auto it = S[v].begin(); it != S[v].end(); it++) S[u].insert(mp(it->first+add[v]-add[u],it->second));
        S[v].clear();
    }
    if (in[u] == 0) {
        for (i = 0; i < queries[u].size(); i++) ans[queries[u][i].second] = S[u].order_of_key(mp(queries[u][i].first-add[u],1e9));
    }
    return 0;
}
LLI bit[400001];
struct data {
    vector<pair<pii,LLI> > vv;
    int update(int i,LLI num) {
        vv.pb(mp(mp(i,-1),num));
        return 0;
    }
    int query(int i,int a,LLI n) {
        vv.pb(mp(mp(i,a),n));
        return 0;
    }
    int process() {
        int i,j;
        for (i = 0; i < vv.size(); i++) {
            if (vv[i].first.second == -1) {
                for (j = vv[i].first.first+1; j <= 400000; j += j & (-j)) bit[j] += vv[i].second;
            }
            else {
                for (j = vv[i].first.first+1; j > 0; j -= j & (-j)) ans[vv[i].first.second] += vv[i].second*bit[j];
            }
        }
        for (i = 0; i < vv.size(); i++) {
            if (vv[i].first.second == -1) {
                for (j = vv[i].first.first+1; j <= 400000; j += j & (-j)) bit[j] = 0;
            }
        }
        vv.clear();
        return 0;
    }
};
data tree1[400001],tree2[400001];
int update(int s,int i,int p,LLI num,LLI num2) {
    for (i++; i <= s; i += i & (-i)) {
        tree1[i].update(p,num);
        tree2[i].update(p,num2);
    }
    return 0;
}
int query(int i,int a,int p,LLI n,LLI n2) {
    for (i++; i > 0; i -= i & (-i)) {
        tree1[i].query(p,a,n);
        tree2[i].query(p,a,n2);
    }
    return 0;
}
int main() {
    int i;
    int N,M,L,C,Q,V;
    LLI T;
    scanf("%d %d %d %d",&N,&M,&L,&C);
    for (i = 0; i < N; i++) scanf("%d",&A[i]);
    for (i = 0; i < M; i++) scanf("%d",&B[i]);
    scanf("%d",&Q);
    for (i = 0; i < Q; i++) {
        scanf("%d %lld",&V,&T);
        queries[V-1].pb(mp(T,i));
    }

    int j = 0;
    for (i = 0; i < 2*N; i++) {
        while ((j <= i) && ((A[i % N]+(i >= N)*L)-(A[j % N]+(j >= N)*L) >= (C % L))) j++;
        if (j > 0) j--;
        if (i >= N) n[i-N] = j % N,t[i-N] = (A[i % N]+(i >= N)*L)-(A[j % N]+(j >= N)*L)+L*(C/L);
    }
    j = 0;
    for (i = 0; i < M; i++) {
        while ((j < N) && (A[j] <= B[i])) j++;
        if (j > 0) j--,S[j].insert(mp(B[i]-A[j],i));
        else S[N-1].insert(mp(B[i]-A[N-1]+L,i));
    }
    for (i = 0; i < N; i++) in[n[i]]++;
    for (i = 0; i < N; i++) {
        if (in[i] == 0) QQ.push(i);
    }
    while (!QQ.empty()) {
        int u = QQ.front();
        QQ.pop();

        in[n[u]]--;
        if (in[n[u]] == 0) QQ.push(n[u]);
    }
    for (i = 0; i < N; i++) {
        if (in[i] == 0) adjList[n[i]].pb(i);
    }
    int k;
    for (i = 0; i < N; i++) {
        if (in[i] > 0) {
            vi cycle;
            int u = i;
            while (in[u] > 0) cycle.pb(u),doDFS(u),in[u] = 0,u = n[u];
            LLI sum = 0;
            vlli poss;
            for (j = cycle.size()-1; j >= 0; j--) {
                sum += t[cycle[j]];
                for (auto it = S[cycle[j]].begin(); it != S[cycle[j]].end(); it++)
                    poss.pb(it->first+add[cycle[j]]+sum);
            }
            LLI sum2 = sum;
            for (j = 0; j < cycle.size(); j++) {
                for (auto it = S[cycle[j]].begin(); it != S[cycle[j]].end(); it++)
                    poss.pb(it->first+add[cycle[j]]+sum2-sum);
                sum2 -= t[cycle[j]];
            }
            if (poss.empty()) continue;
            sort(poss.begin(),poss.end());
            poss.resize(unique(poss.begin(),poss.end())-poss.begin());
            vlli poss2;
            for (j = 0; j < poss.size(); j++) poss2.pb((poss[j]+sum) % sum);
            sort(poss2.begin(),poss2.end());
            poss2.resize(unique(poss2.begin(),poss2.end())-poss2.begin());
            sum2 = 0;
            for (j = cycle.size()-1; j >= 0; j--) {
                sum2 += t[cycle[j]];
                for (auto it = S[cycle[j]].begin(); it != S[cycle[j]].end(); it++) {
                    LLI x = it->first+add[cycle[j]]+sum2;
                    int p = lower_bound(poss.begin(),poss.end(),x)-poss.begin();
                    int q = lower_bound(poss2.begin(),poss2.end(),(x+sum) % sum)-poss2.begin();
                    update(poss.size(),p,q,1,(x+sum)/sum-1);
                }
            }
            for (j = 0; j < cycle.size(); j++) {
                for (auto it = S[cycle[j]].begin(); it != S[cycle[j]].end(); it++) {
                    LLI x = it->first+add[cycle[j]]+sum2;
                    int p = lower_bound(poss.begin(),poss.end(),x)-poss.begin();
                    int q = lower_bound(poss2.begin(),poss2.end(),(x+sum) % sum)-poss2.begin();
                    update(poss.size(),p,q,-1,-((x+sum)/sum-1));
                    x -= sum;
                    p = lower_bound(poss.begin(),poss.end(),x)-poss.begin();
                    q = lower_bound(poss2.begin(),poss2.end(),(x+sum) % sum)-poss2.begin();
                    update(poss.size(),p,q,1,(x+sum)/sum-1);
                }
                for (k = 0; k < queries[cycle[j]].size(); k++) {
                    LLI x = queries[cycle[j]][k].first-(sum-sum2);
                    int p = upper_bound(poss.begin(),poss.end(),x)-poss.begin()-1;
                    int q = upper_bound(poss2.begin(),poss2.end(),(x+sum) % sum)-poss2.begin()-1;
                    query(p,queries[cycle[j]][k].second,poss2.size()-1,(x+sum)/sum-1,-1);
                    query(p,queries[cycle[j]][k].second,q,1,0);
                }
                sum2 -= t[cycle[j]];
            }
            for (j = 1; j <= poss.size(); j++) tree1[j].process(),tree2[j].process();
        }
    }
    for (i = 0; i < Q; i++) printf("%lld\n",ans[i]);

    return 0;
}

Compilation message (stderr)

harvest.cpp: In function 'int doDFS(int)':
harvest.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (i = 0; i < adjList[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
harvest.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (i = 0; i < queries[u].size(); i++) ans[queries[u][i].second] = S[u].order_of_key(mp(queries[u][i].first-add[u],1e9));
      |                     ~~^~~~~~~~~~~~~~~~~~~
harvest.cpp: In member function 'int data::process()':
harvest.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for (i = 0; i < vv.size(); i++) {
      |                     ~~^~~~~~~~~~~
harvest.cpp:108:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for (i = 0; i < vv.size(); i++) {
      |                     ~~^~~~~~~~~~~
harvest.cpp: In function 'int main()':
harvest.cpp:185:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |             for (j = 0; j < cycle.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~
harvest.cpp:194:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |             for (j = 0; j < poss.size(); j++) poss2.pb((poss[j]+sum) % sum);
      |                         ~~^~~~~~~~~~~~~
harvest.cpp:207:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |             for (j = 0; j < cycle.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~
harvest.cpp:218:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |                 for (k = 0; k < queries[cycle[j]].size(); k++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:227:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |             for (j = 1; j <= poss.size(); j++) tree1[j].process(),tree2[j].process();
      |                         ~~^~~~~~~~~~~~~~
harvest.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  136 |     scanf("%d %d %d %d",&N,&M,&L,&C);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:137:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |     for (i = 0; i < N; i++) scanf("%d",&A[i]);
      |                             ~~~~~^~~~~~~~~~~~
harvest.cpp:138:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  138 |     for (i = 0; i < M; i++) scanf("%d",&B[i]);
      |                             ~~~~~^~~~~~~~~~~~
harvest.cpp:139:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  139 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
harvest.cpp:141:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  141 |         scanf("%d %lld",&V,&T);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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