oj.uz

Submission #800010

# Submission time Handle Problem Language Result Execution time Memory
800010 2023-08-01T09:20:33 Z 이동현(#10084) Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 241424 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;
      |             ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 235296 KB Output is correct
2 Correct 98 ms 235864 KB Output is correct
3 Correct 265 ms 235816 KB Output is correct
4 Correct 117 ms 235864 KB Output is correct
5 Correct 205 ms 235924 KB Output is correct
6 Correct 198 ms 236012 KB Output is correct
7 Correct 213 ms 236040 KB Output is correct
8 Correct 98 ms 235796 KB Output is correct
9 Correct 100 ms 235756 KB Output is correct
10 Correct 102 ms 235828 KB Output is correct
11 Correct 105 ms 235740 KB Output is correct
12 Correct 362 ms 235948 KB Output is correct
13 Correct 506 ms 236064 KB Output is correct
14 Correct 286 ms 236004 KB Output is correct
15 Correct 152 ms 236136 KB Output is correct
16 Correct 154 ms 236076 KB Output is correct
17 Correct 159 ms 236100 KB Output is correct
18 Correct 192 ms 236036 KB Output is correct
19 Correct 156 ms 236116 KB Output is correct
20 Correct 161 ms 235948 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 235296 KB Output is correct
2 Correct 98 ms 235864 KB Output is correct
3 Correct 265 ms 235816 KB Output is correct
4 Correct 117 ms 235864 KB Output is correct
5 Correct 205 ms 235924 KB Output is correct
6 Correct 198 ms 236012 KB Output is correct
7 Correct 213 ms 236040 KB Output is correct
8 Correct 98 ms 235796 KB Output is correct
9 Correct 100 ms 235756 KB Output is correct
10 Correct 102 ms 235828 KB Output is correct
11 Correct 105 ms 235740 KB Output is correct
12 Correct 362 ms 235948 KB Output is correct
13 Correct 506 ms 236064 KB Output is correct
14 Correct 286 ms 236004 KB Output is correct
15 Correct 152 ms 236136 KB Output is correct
16 Correct 154 ms 236076 KB Output is correct
17 Correct 159 ms 236100 KB Output is correct
18 Correct 192 ms 236036 KB Output is correct
19 Correct 156 ms 236116 KB Output is correct
20 Correct 161 ms 235948 KB Output is correct
21 Execution timed out 5048 ms 241424 KB Time limit exceeded
22 Halted 0 ms 0 KB -