| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 800002 |
2023-08-01T09:16:59 Z |
이동현(#10084) |
Harvest (JOI20_harvest) |
C++17 |
|
5000 ms |
486928 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;
int INF = (int)1e18;
struct Node{
int l, r, cnt;
Node(){
l = r = cnt = 0;
}
};
int tn;
Node tr[(int)1e7];
void push(int x, int s, int e, int pos){
if(s == e){
++tr[x].cnt;
return;
}
if(pos <= (s + e) / 2){
if(!tr[x].l) tr[x].l = ++tn;
push(tr[x].l, s, (s + e) / 2, pos);
}
else{
if(!tr[x].r) tr[x].r = ++tn;
push(tr[x].r, (s + e) / 2 + 1, e, pos);
}
tr[x].cnt = tr[tr[x].l].cnt + tr[tr[x].r].cnt;
}
int get(int x, int s, int e, int fe){
if(s > fe) return 0;
if(e <= fe){
return tr[x].cnt;
}
int rv = 0;
if(tr[x].l) rv += get(tr[x].l, s, (s + e) / 2, fe);
if(tr[x].r && (s + e) / 2 + 1 <= fe) rv += get(tr[x].r, (s + e) / 2 + 1, e, fe);
return rv;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, l, c;
cin >> n >> m >> l >> c;
vector<int> a(n), b(m);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
for(int i = 0; i < m; ++i){
cin >> b[i];
}
auto god = [&](int x, int y){
return c + (y - c % l - x + l * 2) % l;
};
vector<vector<int>> mine(n);
vector<int> madd(n);
int p = 0;
for(int i = 0; i < n; ++i){
while(p < m && a[i] > b[p]) ++p;
int r = p - 1;
while(r + 1 < m && (i == n - 1 || b[r + 1] < a[i + 1])){
++r;
mine[i].push_back(b[r] - a[i]);
}
p = r;
}
for(int i = 0; i < m && b[i] < a[0]; ++i){
mine[n - 1].push_back(b[i] - a[n - 1] + l);
}
vector<int> got(n);
vector<vector<int>> way(n);
for(int i = 0; i < n; ++i){
int pos = (a[i] - c % l + l) % l;
int p = lower_bound(a.begin(), a.end(), pos + 1) - a.begin();
--p;
if(p < 0) p = n - 1;
got[i] = p;
way[p].push_back(i);
}
int q;
cin >> q;
vector<int> ans(q);
vector<vector<array<int, 2>>> que(n);
for(int i = 0; i < q; ++i){
int x, y;
cin >> x >> y;
--x;
que[x].push_back({y, i});
}
vector<int> cyclen(n, -1);
vector<int> chk(n), cdist(n);
int cn = 0;
auto checkcycle = [&](auto&&self, int x)->void{
if(chk[x]) return;
chk[x] = cn;
if(chk[got[x]] == chk[x]){
int val = cdist[x] - cdist[got[x]] + god(a[got[x]], a[x]);
while(cyclen[x] == -1){
cyclen[x] = val;
x = got[x];
}
return;
}
cdist[got[x]] = cdist[x] + god(a[got[x]], a[x]);
self(self, got[x]);
};
for(int i = 0; i < n; ++i){
++cn;
checkcycle(checkcycle, i);
}
vector<int> ans2(q);
for(int i = 0; i < n; ++i){
vector<int> chk(n);
auto sol = [&](auto&&self, int x, int dist)->void{
if(chk[x]) return;
chk[x] = 1;
for(auto&[t, anspos]:que[i]){
for(auto&j:mine[x]){
if(j + dist > t) continue;
ans2[anspos] += 1 + (cyclen[i] != -1 ? (t - (j + dist)) / cyclen[i] : 0);
}
}
for(auto&nxt:way[x]){
self(self, nxt, dist + god(a[x], a[nxt]));
}
};
sol(sol, i, 0);
}
vector<int> chk1(n);
vector<int> rt(n);
iota(rt.begin(), rt.end(), 1);
tn = n;
auto sol1 = [&](auto&&self, int x)->void{
// assert(cyclen[x] == -1);
if(chk1[x]) return;
chk1[x] = 1;
if(cyclen[x] == -1){
for(auto&i:mine[x]){
push(rt[x], 1, INF, i);
}
}
for(auto&nxt:way[x]){
if(cyclen[nxt] != -1) continue;
self(self, nxt);
// madd[nxt] += god(a[x], a[nxt]);
for(auto&j:mine[nxt]){
j += god(a[x], a[nxt]);
}
// assert(madd[x] >= 0 && madd[nxt] >= 0);
// if((int)mine[x].size() < (int)mine[nxt].size()){
// swap(mine[x], mine[nxt]);
// swap(madd[x], madd[nxt]);
// swap(rt[x], rt[nxt]);
// }
while((int)mine[nxt].size()){
int val = mine[nxt].back() + madd[nxt] - madd[x];
mine[x].push_back(val);
if(cyclen[x] == -1 && val + madd[x] <= INF){
push(rt[x], 1, INF, val);
}
mine[nxt].pop_back();
}
}
if(cyclen[x] == -1){
for(auto&[t, anspos]:que[x]){
int sum = get(rt[x], 1, INF, t - madd[x]);
// ans[anspos] += get(rt[x], 1, INF, t - madd[x]);
for(auto&j:mine[x]){
if(j + madd[x] > t) continue;
ans[anspos] += 1;
--sum;
}
// if(sum) while(true){}
}
}
};
for(int i = 0; i < n; ++i){
if(cyclen[i] != -1) continue;
sol1(sol1, i);
}
for(int i = 0; i < n; ++i){
if(cyclen[i] == -1) continue;
sol1(sol1, i);
sort(mine[i].begin(), mine[i].end());
for(auto&j:mine[i]){
j += madd[i];
}
while((int)mine[i].size() && mine[i].back() > INF){
mine[i].pop_back();
}
}
vector<int> didcycle(n);
for(int i = 0; i < n; ++i){
if(cyclen[i] == -1) continue;
vector<int> cycle;
int now = i;
while(true){
cycle.push_back(now);
int nxt = -1;
for(auto&j:way[now]){
if(cyclen[j] != -1){
nxt = j;
break;
}
}
// assert(nxt != -1);
now = nxt;
if(now == i) break;
}
int dsum = 0;
int nrt = ++tn;
for(int j = 0; j < (int)cycle.size(); ++j){
for(auto&x:mine[cycle[j]]){
for(auto&[t, anspos]:que[i]){
int val = x + dsum;
if(val <= t) ans[anspos] += 1 + (t - val) / cyclen[i];
}
// push(nrt, 1, INF, x + dsum);
}
if(j + 1 < (int)cycle.size()){
dsum += god(a[cycle[j]], a[cycle[j + 1]]);
}
}
// for(int j = 0; j < (int)cycle.size(); ++j){
// for(auto&[t, anspos]:que[cycle[j]]){
// ans[anspos] += get(nrt, 1, INF, t);
// }
// }
}
for(int i = 0; i < q; ++i){
cout << ans[i] << '\n';
}
for(int i = 0; i < n; ++i){
if(cyclen[i] != -1) continue;
for(auto&[t, anspos]:que[i]){
assert(ans[anspos] == ans2[anspos]);
}
}
return 0;
}
Compilation message
harvest.cpp: In function 'int main()':
harvest.cpp:259:13: warning: unused variable 'nrt' [-Wunused-variable]
259 | int nrt = ++tn;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
235468 KB |
Output is correct |
| 2 |
Correct |
99 ms |
235796 KB |
Output is correct |
| 3 |
Correct |
253 ms |
235848 KB |
Output is correct |
| 4 |
Correct |
186 ms |
237828 KB |
Output is correct |
| 5 |
Runtime error |
521 ms |
486928 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5083 ms |
241484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
235468 KB |
Output is correct |
| 2 |
Correct |
99 ms |
235796 KB |
Output is correct |
| 3 |
Correct |
253 ms |
235848 KB |
Output is correct |
| 4 |
Correct |
186 ms |
237828 KB |
Output is correct |
| 5 |
Runtime error |
521 ms |
486928 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
