oj.uz

Submission #513439

# Submission time Handle Problem Language Result Execution time Memory
513439 2022-01-17T06:24:53 Z wiwiho Harvest (JOI20_harvest) C++14
5 / 100
 5000 ms 173812 KB 
#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);
    vector<pll> ta(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] = L - a[i];
        if(a[i] == L) a[i] = 0;
        ta[i] = mp(a[i], i);
    }
    for(int i = 1; i <= m; i++){
        cin >> b[i];
        b[i] = L - b[i];
        if(b[i] == L) b[i] = 0;
    }
    lsort(a);
    lsort(b);
    lsort(ta);
    vector<int> id(n + 1);
    for(int i = 1; i <= n; i++){
        id[ta[i].S] = i;
    }

    //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 = id[v];

        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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 13 ms 672 KB Output is correct
3 Correct 97 ms 760 KB Output is correct
4 Correct 25 ms 8504 KB Output is correct
5 Correct 123 ms 87220 KB Output is correct
6 Correct 115 ms 86340 KB Output is correct
7 Correct 137 ms 88208 KB Output is correct
8 Correct 12 ms 716 KB Output is correct
9 Correct 12 ms 720 KB Output is correct
10 Correct 12 ms 844 KB Output is correct
11 Correct 12 ms 828 KB Output is correct
12 Correct 266 ms 173812 KB Output is correct
13 Correct 321 ms 173764 KB Output is correct
14 Correct 162 ms 90292 KB Output is correct
15 Correct 65 ms 47744 KB Output is correct
16 Correct 64 ms 47540 KB Output is correct
17 Correct 70 ms 48964 KB Output is correct
18 Correct 66 ms 45232 KB Output is correct
19 Correct 62 ms 46336 KB Output is correct
20 Correct 60 ms 43484 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5036 ms 3096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 13 ms 672 KB Output is correct
3 Correct 97 ms 760 KB Output is correct
4 Correct 25 ms 8504 KB Output is correct
5 Correct 123 ms 87220 KB Output is correct
6 Correct 115 ms 86340 KB Output is correct
7 Correct 137 ms 88208 KB Output is correct
8 Correct 12 ms 716 KB Output is correct
9 Correct 12 ms 720 KB Output is correct
10 Correct 12 ms 844 KB Output is correct
11 Correct 12 ms 828 KB Output is correct
12 Correct 266 ms 173812 KB Output is correct
13 Correct 321 ms 173764 KB Output is correct
14 Correct 162 ms 90292 KB Output is correct
15 Correct 65 ms 47744 KB Output is correct
16 Correct 64 ms 47540 KB Output is correct
17 Correct 70 ms 48964 KB Output is correct
18 Correct 66 ms 45232 KB Output is correct
19 Correct 62 ms 46336 KB Output is correct
20 Correct 60 ms 43484 KB Output is correct
21 Execution timed out 5036 ms 3096 KB Time limit exceeded
22 Halted 0 ms 0 KB -