| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 232705 |
2020-05-17T22:16:17 Z |
duality |
Harvest (JOI20_harvest) |
C++11 |
|
114 ms |
55004 KB |
#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;
}
Compilation message
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);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
43 ms |
48376 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
114 ms |
55004 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
43 ms |
48376 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
