| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 398184 |
2021-05-03T21:26:15 Z |
duality |
Harvest (JOI20_harvest) |
C++11 |
|
5000 ms |
109088 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) {
tree1[1].update(p,num);
tree2[1].update(p,num2);
return 0;
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) {
tree1[1].query(p,a,n);
tree2[1].query(p,a,n2);
return 0;
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:191:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
191 | for (j = 0; j < cycle.size(); j++) {
| ~~^~~~~~~~~~~~~~
harvest.cpp:200:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
200 | for (j = 0; j < poss.size(); j++) poss2.pb((poss[j]+sum) % sum);
| ~~^~~~~~~~~~~~~
harvest.cpp:213:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
213 | for (j = 0; j < cycle.size(); j++) {
| ~~^~~~~~~~~~~~~~
harvest.cpp:224: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]
224 | for (k = 0; k < queries[cycle[j]].size(); k++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:233:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
233 | for (j = 1; j <= poss.size(); j++) tree1[j].process(),tree2[j].process();
| ~~^~~~~~~~~~~~~~
harvest.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
142 | scanf("%d %d %d %d",&N,&M,&L,&C);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:143:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
143 | for (i = 0; i < N; i++) scanf("%d",&A[i]);
| ~~~~~^~~~~~~~~~~~
harvest.cpp:144:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
144 | for (i = 0; i < M; i++) scanf("%d",&B[i]);
| ~~~~~^~~~~~~~~~~~
harvest.cpp:145:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
145 | scanf("%d",&Q);
| ~~~~~^~~~~~~~~
harvest.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
147 | scanf("%d %lld",&V,&T);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
47812 KB |
Output is correct |
| 2 |
Correct |
38 ms |
47684 KB |
Output is correct |
| 3 |
Correct |
45 ms |
48460 KB |
Output is correct |
| 4 |
Incorrect |
63 ms |
48672 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
174 ms |
75476 KB |
Output is correct |
| 2 |
Correct |
555 ms |
65824 KB |
Output is correct |
| 3 |
Correct |
213 ms |
58740 KB |
Output is correct |
| 4 |
Correct |
229 ms |
78620 KB |
Output is correct |
| 5 |
Execution timed out |
5077 ms |
109088 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
47812 KB |
Output is correct |
| 2 |
Correct |
38 ms |
47684 KB |
Output is correct |
| 3 |
Correct |
45 ms |
48460 KB |
Output is correct |
| 4 |
Incorrect |
63 ms |
48672 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
