| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 398183 |
2021-05-03T21:23:22 Z |
duality |
Harvest (JOI20_harvest) |
C++11 |
|
5000 ms |
155988 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>;
#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()) 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[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
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);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
47948 KB |
Output is correct |
| 2 |
Correct |
40 ms |
47680 KB |
Output is correct |
| 3 |
Correct |
54 ms |
51536 KB |
Output is correct |
| 4 |
Correct |
74 ms |
50196 KB |
Output is correct |
| 5 |
Correct |
493 ms |
51048 KB |
Output is correct |
| 6 |
Correct |
481 ms |
51152 KB |
Output is correct |
| 7 |
Correct |
482 ms |
51060 KB |
Output is correct |
| 8 |
Correct |
50 ms |
49732 KB |
Output is correct |
| 9 |
Correct |
49 ms |
49868 KB |
Output is correct |
| 10 |
Correct |
51 ms |
49772 KB |
Output is correct |
| 11 |
Correct |
48 ms |
49996 KB |
Output is correct |
| 12 |
Correct |
56 ms |
51364 KB |
Output is correct |
| 13 |
Correct |
53 ms |
51328 KB |
Output is correct |
| 14 |
Correct |
51 ms |
49804 KB |
Output is correct |
| 15 |
Correct |
262 ms |
50624 KB |
Output is correct |
| 16 |
Correct |
265 ms |
50660 KB |
Output is correct |
| 17 |
Correct |
260 ms |
50628 KB |
Output is correct |
| 18 |
Correct |
276 ms |
50708 KB |
Output is correct |
| 19 |
Correct |
273 ms |
50656 KB |
Output is correct |
| 20 |
Correct |
266 ms |
50808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
346 ms |
152832 KB |
Output is correct |
| 2 |
Correct |
543 ms |
69016 KB |
Output is correct |
| 3 |
Correct |
206 ms |
58692 KB |
Output is correct |
| 4 |
Correct |
397 ms |
155988 KB |
Output is correct |
| 5 |
Execution timed out |
5051 ms |
109364 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
47948 KB |
Output is correct |
| 2 |
Correct |
40 ms |
47680 KB |
Output is correct |
| 3 |
Correct |
54 ms |
51536 KB |
Output is correct |
| 4 |
Correct |
74 ms |
50196 KB |
Output is correct |
| 5 |
Correct |
493 ms |
51048 KB |
Output is correct |
| 6 |
Correct |
481 ms |
51152 KB |
Output is correct |
| 7 |
Correct |
482 ms |
51060 KB |
Output is correct |
| 8 |
Correct |
50 ms |
49732 KB |
Output is correct |
| 9 |
Correct |
49 ms |
49868 KB |
Output is correct |
| 10 |
Correct |
51 ms |
49772 KB |
Output is correct |
| 11 |
Correct |
48 ms |
49996 KB |
Output is correct |
| 12 |
Correct |
56 ms |
51364 KB |
Output is correct |
| 13 |
Correct |
53 ms |
51328 KB |
Output is correct |
| 14 |
Correct |
51 ms |
49804 KB |
Output is correct |
| 15 |
Correct |
262 ms |
50624 KB |
Output is correct |
| 16 |
Correct |
265 ms |
50660 KB |
Output is correct |
| 17 |
Correct |
260 ms |
50628 KB |
Output is correct |
| 18 |
Correct |
276 ms |
50708 KB |
Output is correct |
| 19 |
Correct |
273 ms |
50656 KB |
Output is correct |
| 20 |
Correct |
266 ms |
50808 KB |
Output is correct |
| 21 |
Correct |
346 ms |
152832 KB |
Output is correct |
| 22 |
Correct |
543 ms |
69016 KB |
Output is correct |
| 23 |
Correct |
206 ms |
58692 KB |
Output is correct |
| 24 |
Correct |
397 ms |
155988 KB |
Output is correct |
| 25 |
Execution timed out |
5051 ms |
109364 KB |
Time limit exceeded |
| 26 |
Halted |
0 ms |
0 KB |
- |
