| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 398181 |
2021-05-03T21:17:40 Z |
duality |
Harvest (JOI20_harvest) |
C++11 |
|
5000 ms |
143384 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 ----------
#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>;
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()) swap(S[v],S[u]),swap(add[v],add[u]);
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[400000];
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[1 << 20],tree2[1 << 20];
int update(int s,int e,int ai,int i,int p,LLI num,LLI num2) {
if ((s > ai) || (e < ai)) return 0;
else if (s == e) {
tree1[i].update(p,num);
tree2[i].update(p,num2);
return 0;
}
int mid = (s+e) / 2;
tree1[i].update(p,num);
tree2[i].update(p,num2);
update(s,mid,ai,2*i+1,p,num,num2),update(mid+1,e,ai,2*i+2,p,num,num2);
return 0;
}
int query(int s,int e,int qs,int qe,int i,int a,int p,LLI n,LLI n2) {
if ((s > qe) || (e < qs)) return 0;
else if ((s >= qs) && (e <= qe)) {
tree1[i].query(p,a,n);
tree2[i].query(p,a,n2);
return 0;
}
int mid = (s+e) / 2;
query(s,mid,qs,qe,2*i+1,a,p,n,n2);
query(mid+1,e,qs,qe,2*i+2,a,p,n,n2);
return 0;
}
int process(int s,int e,int i) {
if (s == e) {
tree1[i].process();
tree2[i].process();
return 0;
}
int mid = (s+e) / 2;
process(s,mid,2*i+1),process(mid+1,e,2*i+2);
tree1[i].process();
tree2[i].process();
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(0,poss.size()-1,p,0,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(0,poss.size()-1,p,0,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(0,poss.size()-1,p,0,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(0,poss.size()-1,0,p,0,queries[cycle[j]][k].second,poss2.size()-1,(x+sum)/sum-1,-1);
query(0,poss.size()-1,0,p,0,queries[cycle[j]][k].second,q,1,0);
}
sum2 -= t[cycle[j]];
}
process(0,poss.size()-1,0);
}
}
for (i = 0; i < Q; i++) printf("%lld\n",ans[i]);
return 0;
}
Compilation message
harvest.cpp: In function 'int doDFS(int)':
harvest.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (i = 0; i < adjList[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~
harvest.cpp:82: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]
82 | 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:99: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]
99 | for (i = 0; i < vv.size(); i++) {
| ~~^~~~~~~~~~~
harvest.cpp:107: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]
107 | for (i = 0; i < vv.size(); i++) {
| ~~^~~~~~~~~~~
harvest.cpp: In function 'int main()':
harvest.cpp:210:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
210 | for (j = 0; j < cycle.size(); j++) {
| ~~^~~~~~~~~~~~~~
harvest.cpp:219:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
219 | for (j = 0; j < poss.size(); j++) poss2.pb((poss[j]+sum) % sum);
| ~~^~~~~~~~~~~~~
harvest.cpp:232:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
232 | for (j = 0; j < cycle.size(); j++) {
| ~~^~~~~~~~~~~~~~
harvest.cpp:243: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]
243 | for (k = 0; k < queries[cycle[j]].size(); k++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:161:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
161 | scanf("%d %d %d %d",&N,&M,&L,&C);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:162:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
162 | for (i = 0; i < N; i++) scanf("%d",&A[i]);
| ~~~~~^~~~~~~~~~~~
harvest.cpp:163:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
163 | for (i = 0; i < M; i++) scanf("%d",&B[i]);
| ~~~~~^~~~~~~~~~~~
harvest.cpp:164:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
164 | scanf("%d",&Q);
| ~~~~~^~~~~~~~~
harvest.cpp:166:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
166 | scanf("%d %lld",&V,&T);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
78284 KB |
Output is correct |
| 2 |
Correct |
60 ms |
78184 KB |
Output is correct |
| 3 |
Correct |
89 ms |
83700 KB |
Output is correct |
| 4 |
Correct |
104 ms |
83996 KB |
Output is correct |
| 5 |
Correct |
526 ms |
84900 KB |
Output is correct |
| 6 |
Correct |
508 ms |
84852 KB |
Output is correct |
| 7 |
Correct |
534 ms |
84856 KB |
Output is correct |
| 8 |
Correct |
85 ms |
83516 KB |
Output is correct |
| 9 |
Correct |
84 ms |
83516 KB |
Output is correct |
| 10 |
Correct |
84 ms |
83512 KB |
Output is correct |
| 11 |
Correct |
87 ms |
83516 KB |
Output is correct |
| 12 |
Correct |
88 ms |
85012 KB |
Output is correct |
| 13 |
Correct |
87 ms |
83596 KB |
Output is correct |
| 14 |
Correct |
84 ms |
80724 KB |
Output is correct |
| 15 |
Correct |
303 ms |
84508 KB |
Output is correct |
| 16 |
Correct |
336 ms |
84560 KB |
Output is correct |
| 17 |
Correct |
298 ms |
84608 KB |
Output is correct |
| 18 |
Correct |
309 ms |
84432 KB |
Output is correct |
| 19 |
Correct |
312 ms |
84568 KB |
Output is correct |
| 20 |
Correct |
313 ms |
84504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
261 ms |
104592 KB |
Output is correct |
| 2 |
Correct |
619 ms |
101232 KB |
Output is correct |
| 3 |
Correct |
235 ms |
89156 KB |
Output is correct |
| 4 |
Correct |
293 ms |
114920 KB |
Output is correct |
| 5 |
Execution timed out |
5062 ms |
143384 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
78284 KB |
Output is correct |
| 2 |
Correct |
60 ms |
78184 KB |
Output is correct |
| 3 |
Correct |
89 ms |
83700 KB |
Output is correct |
| 4 |
Correct |
104 ms |
83996 KB |
Output is correct |
| 5 |
Correct |
526 ms |
84900 KB |
Output is correct |
| 6 |
Correct |
508 ms |
84852 KB |
Output is correct |
| 7 |
Correct |
534 ms |
84856 KB |
Output is correct |
| 8 |
Correct |
85 ms |
83516 KB |
Output is correct |
| 9 |
Correct |
84 ms |
83516 KB |
Output is correct |
| 10 |
Correct |
84 ms |
83512 KB |
Output is correct |
| 11 |
Correct |
87 ms |
83516 KB |
Output is correct |
| 12 |
Correct |
88 ms |
85012 KB |
Output is correct |
| 13 |
Correct |
87 ms |
83596 KB |
Output is correct |
| 14 |
Correct |
84 ms |
80724 KB |
Output is correct |
| 15 |
Correct |
303 ms |
84508 KB |
Output is correct |
| 16 |
Correct |
336 ms |
84560 KB |
Output is correct |
| 17 |
Correct |
298 ms |
84608 KB |
Output is correct |
| 18 |
Correct |
309 ms |
84432 KB |
Output is correct |
| 19 |
Correct |
312 ms |
84568 KB |
Output is correct |
| 20 |
Correct |
313 ms |
84504 KB |
Output is correct |
| 21 |
Correct |
261 ms |
104592 KB |
Output is correct |
| 22 |
Correct |
619 ms |
101232 KB |
Output is correct |
| 23 |
Correct |
235 ms |
89156 KB |
Output is correct |
| 24 |
Correct |
293 ms |
114920 KB |
Output is correct |
| 25 |
Execution timed out |
5062 ms |
143384 KB |
Time limit exceeded |
| 26 |
Halted |
0 ms |
0 KB |
- |
