oj.uz

답안 #799996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
799996 2023-08-01T09:13:51 Z 이동현(#10084) 수확 (JOI20_harvest) C++17
5 / 100
 5000 ms 241444 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]);

            // 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:256:13: warning: unused variable 'nrt' [-Wunused-variable]
  256 |         int nrt = ++tn;
      |             ^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 235372 KB Output is correct
2 Correct 95 ms 235980 KB Output is correct
3 Correct 254 ms 235928 KB Output is correct
4 Correct 103 ms 235808 KB Output is correct
5 Correct 158 ms 236040 KB Output is correct
6 Correct 158 ms 236116 KB Output is correct
7 Correct 174 ms 236128 KB Output is correct
8 Correct 96 ms 235900 KB Output is correct
9 Correct 94 ms 235872 KB Output is correct
10 Correct 97 ms 235852 KB Output is correct
11 Correct 103 ms 235844 KB Output is correct
12 Correct 357 ms 236224 KB Output is correct
13 Correct 549 ms 236152 KB Output is correct
14 Correct 261 ms 236084 KB Output is correct
15 Correct 127 ms 236112 KB Output is correct
16 Correct 128 ms 235984 KB Output is correct
17 Correct 132 ms 236128 KB Output is correct
18 Correct 133 ms 236032 KB Output is correct
19 Correct 133 ms 235996 KB Output is correct
20 Correct 143 ms 235960 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5064 ms 241444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 235372 KB Output is correct
2 Correct 95 ms 235980 KB Output is correct
3 Correct 254 ms 235928 KB Output is correct
4 Correct 103 ms 235808 KB Output is correct
5 Correct 158 ms 236040 KB Output is correct
6 Correct 158 ms 236116 KB Output is correct
7 Correct 174 ms 236128 KB Output is correct
8 Correct 96 ms 235900 KB Output is correct
9 Correct 94 ms 235872 KB Output is correct
10 Correct 97 ms 235852 KB Output is correct
11 Correct 103 ms 235844 KB Output is correct
12 Correct 357 ms 236224 KB Output is correct
13 Correct 549 ms 236152 KB Output is correct
14 Correct 261 ms 236084 KB Output is correct
15 Correct 127 ms 236112 KB Output is correct
16 Correct 128 ms 235984 KB Output is correct
17 Correct 132 ms 236128 KB Output is correct
18 Correct 133 ms 236032 KB Output is correct
19 Correct 133 ms 235996 KB Output is correct
20 Correct 143 ms 235960 KB Output is correct
21 Execution timed out 5064 ms 241444 KB Time limit exceeded
22 Halted 0 ms 0 KB -