Submission #513417

#	Time	Username	Problem	Language	Result	Execution time	Memory
513417		wiwiho	Harvest (JOI20_harvest)	C++14	0 / 100	5099 ms	3464 KiB

harvest

#include <bits/stdc++.h>

#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

ostream& operator<<(ostream& o, pll p){
    return o << '(' << p.F << ',' << p.S << ')';
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    ll L, C;
    cin >> n >> m >> L >> C;

    vector<ll> a(n + 1), b(m + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] = L - a[i];
    }
    for(int i = 1; i <= m; i++){
        cin >> b[i];
        b[i] = L - b[i];
    }
    reverse(a.begin() + 1, a.end());
    reverse(b.begin() + 1, b.end());

    //printv(a, cerr);
    //printv(b, cerr);

    vector<int> g(n + 1), gt(n + 1);

    for(int i = 1; i <= n; i++){
        ll tmp = a[i] + C;
        tmp %= L;
        auto it = lower_bound(a.begin() + 1, a.end(), tmp);
        if(it == a.end()) it = a.begin() + 1;
        int nxt = it - a.begin();
        g[i] = nxt;
        if(tmp <= a[nxt]) gt[i] = C + a[nxt] - tmp;
        else gt[i] = C + L - tmp + a[nxt];
    }

    //printv(g, cerr);
    //printv(gt, cerr);

    vector<vector<pll>> apple(n + 1);

    for(int i = 1; i <= m; i++){
        auto it = lower_bound(a.begin() + 1, a.end(), b[i]);
        if(it == a.end()) it = a.begin() + 1;
        int now = it - a.begin();

        vector<ll> arr(n + 1, -1), per(n + 1, -1);
        ll tm = (a[now] - b[i] + L) % L;
        while(true){
            if(arr[now] == -1) arr[now] = tm;
            else if(per[now] == -1) per[now] = tm - arr[now];
            else break;
            tm += gt[now];
            now = g[now];
        }

        for(int j = 1; j <= n; j++){
            if(arr[j] == -1) continue;
            apple[j].eb(mp(arr[j], per[j]));
        }

        /*cerr << "OAO " << i << "\n";
        printv(arr, cerr);
        printv(per, cerr);*/
    }

    /*for(int i = 1; i <= n; i++){
        printv(apple[i], cerr);
    }*/

    int q;
    cin >> q;
    while(q--){
        
        ll v, t;
        cin >> v >> t;
        v = n - v + 1;

        ll ans = 0;
        for(pll i : apple[v]){
            if(i.F > t) continue;
            ans++;
            if(i.S != -1){
                ans += (t - i.F) / i.S;
            }
        }
        cout << ans << "\n";

    }
    
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 75