제출 #232706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
232706		duality	수확 (JOI20_harvest)	C++11	0 / 100	110 ms	28136 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 ----------

int A[200000],B[200000];
vector<pair<LLI,int> > queries[200000];
int N,L;
int dist(int a,int b) {
    a += 2*N,b += 2*N;
    return ((A[b % N]-A[a % N]+L) % L)+L*((b-a)/N);
}
int n[200000];
vpii adjList[200000];
int in[200000];
queue<int> QQ;
vi vv[200000];
LLI ans[200000];
struct node {
    node *l,*r;
    int s,p;
    LLI k;
};
int size(node *n) {
    if (n == NULL) return 0;
    else return n->s;
}
int update(node *n) {
    if (n != NULL) n->s = size(n->l) + size(n->r) + 1;
    return 0;
}
int merge(node *l,node *r,node *&n) {
    if (l == NULL) n = r;
    else if (r == NULL) n = l;
    else if (l->p > r->p) merge(l->r,r,l->r),n = l;
    else merge(l,r->l,r->l),n = r;
    update(n);
    return 0;
}
int split(node *n,node *&l,node *&r,LLI k) {
    if (n == NULL) l = r = NULL;
    else if (k < n->k) split(n->l,l,n->l,k),r = n;
    else split(n->r,n->r,r,k),l = n;
    update(l),update(r);
    return 0;
}
vlli all;
int inorder(node *n,LLI add) {
    if (n == NULL) return 0;
    inorder(n->l,add);
    all.pb(n->k+add);
    inorder(n->r,add);
    return 0;
}
node *root[200000];
LLI toAdd[200000];
int doDFS(int u) {
    int i;
    vpii c;
    c.pb(mp(u,0));
    for (i = 0; i < vv[u].size(); i++) {
        node *n = new node,*l,*r;
        n->l = n->r = NULL;
        n->k = vv[u][i],n->s = 1,n->p = rand();
        split(root[u],l,r,n->k);
        merge(l,n,l),merge(l,r,root[u]);
    }
    //cout<<u<<":"<<size(root[u])<<endl;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i].first;
        //cout<<u<<"-->"<<v<<": "<<adjList[u][i].second<<endl;
        if (in[v] == 0) c.pb(mp(v,adjList[u][i].second)),doDFS(v);
    }
    for (i = 0; i < c.size(); i++) {
        if (size(root[c[i].first]) > size(root[c[0].first])) swap(c[i],c[0]);
    }
    for (i = 1; i < c.size(); i++) inorder(root[c[i].first],toAdd[c[i].first]+c[i].second);
    /*cout<<"c:"<<endl;
    for (i = 0; i < c.size() ;i++){
        cout << c[i].first<<","<<c[i].second<<" ";
    }
    cout << endl;*/
    toAdd[c[0].first] += c[0].second;
    for (i = 0; i < all.size(); i++) {
        node *n = new node,*l,*r;
        n->l = n->r = NULL;
        n->k = all[i]-toAdd[c[0].first],n->s = 1,n->p = rand();
        split(root[c[0].first],l,r,n->k);
        merge(l,n,l),merge(l,r,root[c[0].first]);
    }
    all.clear();
    root[u] = root[c[0].first],toAdd[u] = toAdd[c[0].first];
    //cout<<"u:"<<u<<"in:"<<in[u]<<endl;
    //if (root[u] != NULL) cout << root[u]->k+toAdd[u]<<endl;
    if (in[u] == 0) {
        for (i = 0; i < queries[u].size(); i++) {
            //cout<<"qq:"<<queries[u][i].second<<endl;
            node *l,*r;
            split(root[u],l,r,queries[u][i].first-toAdd[u]);
            ans[queries[u][i].second] = size(l);
            merge(l,r,root[u]);
        }
    }

    //cout<<u<<":"<<size(root[u])<<endl;
    return 0;
}
vpii cycle;
vlli dists[400005];
LLI pre[400005];
int main() {
    int i;
    int M,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 = -N,k;
    C %= L;
    for (i = 0; i < N; i++) {
        while (dist(j,i) >= C) j++;
        n[i] = (j+N-1) % N,in[n[i]]++;
        //cout<<n[i]<<endl;
        adjList[n[i]].pb(mp(i,(A[i]-A[n[i]]+L) % L));
    }
    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 < M; i++) {
        int u = upper_bound(A,A+N,B[i])-A-1;
        if (u == -1) u = N-1;
        vv[u].pb((B[i]-A[u]+L) % L);
    }
    for (i = 0; i < N; i++) {
        if (in[i] != 0) doDFS(i);
    }
    for (i = 0; i < N; i++) {
        if (in[i] != 0) {
            int u = i;
            while (in[u] != 0) {
                cycle.pb(mp(u,((A[u]-A[n[u]]+L) % L)));
                in[u] = 0,u = n[u];
            }
            for (j = 0; j < cycle.size(); j++) {
                //cout<<cycle[j].first<<","<<cycle[j].second<<endl;
                //inorder(root[cycle[j].first],toAdd[cycle[j].first]);
                //dists[j] = all,all.clear();
                pre[j+1] = pre[j]+cycle[j].second;
            }
            pre[0] = 0;
            for (j = 0; j < cycle.size(); j++) pre[j+cycle.size()] = pre[j]+pre[cycle.size()],dists[j+cycle.size()] = dists[j];
            /*for (j = 0; j < 2*cycle.size(); j++) cout << pre[j] << " ";
            cout << endl;
            for (j = 0; j < 2*cycle.size(); j++) {
                for (k = 0; k < dists[j].size(); k++) {
                    cout << dists[j][k] << " ";
                }
                cout << endl;
            }*/
            for (j = 0; j < cycle.size(); j++) {
                int u = cycle[j].first;
                for (k = 0; k < queries[u].size(); k++) {
                    int l,m;
                    for (l = j+1; l <= j+cycle.size(); l++) {
                        for (m = 0; m < dists[l].size(); m++) {
                            LLI T = queries[u][k].first-dists[l][m]-(pre[j+cycle.size()]-pre[l]);
                            //cout<<T<<",";
                            if (T >= 0) ans[queries[u][k].second] += T/pre[cycle.size()]+1;
                        }
                    }
                }
            }
/*
            for (j = 0; j < cycle.size(); j++) {
                cout<<cycle[j]<<" ";
                int s = all.size();
                inorder(root[cycle[j]],toAdd[cycle[j]]);
                for (k = s; k < all.size(); k++) pre2[k] = pre[j];
            }
            cout << endl;
            for (j = 0; j < all.size(); j++) cout << all[j] << " ";
            cout << endl;
            int s = all.size();
            for (j = 0; j < s; j++) all.pb(all[j]),pre2[all.size()-1] = pre2[j]+pre[cycle.size()];
            for (j = 0; j < cycle.size(); j++) {
                int u = cycle[j];
                for (k = 0; k < queries[u].size(); k++) {
                    int l;
                    for (l = 0; l < all.size(); l++) {
                        //if ()
                    }
                    //queries[u][k]
                }
            }
            all.clear();*/
            for (j = 0; j < 2*cycle.size(); j++) dists[j].clear();
            cycle.clear();
        }
    }
    for (i = 0; i < Q; i++) printf("%lld\n",ans[i]);

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

harvest.cpp: In function 'int doDFS(int)':
harvest.cpp:113:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < vv[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~
harvest.cpp:121:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
harvest.cpp:126:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < c.size(); i++) {
                 ~~^~~~~~~~~~
harvest.cpp:129:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < c.size(); i++) inorder(root[c[i].first],toAdd[c[i].first]+c[i].second);
                 ~~^~~~~~~~~~
harvest.cpp:136:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < all.size(); i++) {
                 ~~^~~~~~~~~~~~
harvest.cpp:148:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < queries[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
harvest.cpp: In function 'int main()':
harvest.cpp:209:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < cycle.size(); j++) {
                         ~~^~~~~~~~~~~~~~
harvest.cpp:216:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < cycle.size(); j++) pre[j+cycle.size()] = pre[j]+pre[cycle.size()],dists[j+cycle.size()] = dists[j];
                         ~~^~~~~~~~~~~~~~
harvest.cpp:225:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < cycle.size(); j++) {
                         ~~^~~~~~~~~~~~~~
harvest.cpp:227:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (k = 0; k < queries[u].size(); k++) {
                             ~~^~~~~~~~~~~~~~~~~~~
harvest.cpp:229:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (l = j+1; l <= j+cycle.size(); l++) {
                                   ~~^~~~~~~~~~~~~~~~~
harvest.cpp:230:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for (m = 0; m < dists[l].size(); m++) {
                                     ~~^~~~~~~~~~~~~~~~~
harvest.cpp:261:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < 2*cycle.size(); j++) dists[j].clear();
                         ~~^~~~~~~~~~~~~~~~
harvest.cpp:167:10: 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,&C);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:168:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < N; i++) scanf("%d",&A[i]);
                             ~~~~~^~~~~~~~~~~~
harvest.cpp:169:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < M; i++) scanf("%d",&B[i]);
                             ~~~~~^~~~~~~~~~~~
harvest.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&Q);
     ~~~~~^~~~~~~~~
harvest.cpp:172:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %lld",&V,&T);
         ~~~~~^~~~~~~~~~~~~~~~~

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