oj.uz

Submission #799991

# Submission time Handle Problem Language Result Execution time Memory
799991 2023-08-01T09:11:16 Z 반딧불(#10081) Harvest (JOI20_harvest) C++17
25 / 100
 503 ms 127404 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void input();
void getPersonInfo();
void organizeTree();
void getAppleInfo();
void inputQuery();
void solve();
void output();

int main(){
    input();
    getPersonInfo();
    organizeTree();
    getAppleInfo();
    inputQuery();
    solve();
    output();
}

int n, k, q; ll L, C;
ll a[200002], b[200002];

void input(){
    scanf("%d %d %lld %lld", &n, &k, &L, &C);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
    for(int i=1; i<=k; i++) scanf("%lld", &b[i]);
}

int nxt[200002]; ll delay[200002];
int par[200002]; bool inCycle[200002]; /// inCycle�� 0�� ��츸 par�� 0�� �ƴϴ�
ll dist[200002];
int cycleNum[200002], cycleIdx[200002];

vector<int> cycle[200002]; /// ����Ŭ�� ��� ���
vector<ll> cycleT[200002]; /// ���������� �� �������� ��ȸ�ϴ� �� �ɸ��� �ð�
ll cycleLength[200002]; /// �� ����Ŭ�� �ѷ�

int findNxt(ll t){ /// t ������ �
    int idx = upper_bound(a+1, a+n+1, t) - a - 1;
    if(idx == 0) idx = n;
    return idx;
}

ll findNxtTime(ll s, ll mod){
    return (s-mod+L-1)/L*L+mod;
}

void getPersonInfo(){
    for(int i=1; i<=n; i++){
        nxt[i] = findNxt((a[i]-C%L+L)%L);
        delay[i] = findNxtTime(C, (a[i] - a[nxt[i]] + L) % L);
    }

    vector<int> visited (n+1);
    for(int i=1; i<=n; i++){
        if(visited[i]) continue;
        vector<int> history;
        int x = i; ll timeSum = 0;
        while(true){
            if(visited[x]){ /// ��
                if(visited[x] == i){ /// ���ο� ����Ŭ�� ã�Ҵ�
                    int idx = find(history.begin(), history.end(), x) - history.begin();
                    /// [idx, end) �κ��� �׳� ����Ŭ�� ������ �ȴ�
                    for(int i=idx; i<(int)history.size(); i++){
                        cycle[x].push_back(history[i]);
                        cycleT[x].push_back(cycleLength[x]);
                        cycleNum[history[i]] = x, cycleIdx[history[i]] = i-idx, inCycle[history[i]] = true;
                        cycleLength[x] += delay[history[i]];
                    }
                    /// �޺κ��� �׳� Ʈ��
                    int pr = x;
                    for(int i=idx-1; i>=0; i--){
                        par[history[i]] = pr, dist[history[i]] = dist[pr] + delay[history[i]];
                        cycleNum[history[i]] = cycleNum[pr], cycleIdx[history[i]] = cycleIdx[pr];
                        pr = history[i];
                    }
                }
                else{ /// �׳� Ʈ�� �Ϻκ��� ã�Ҵ�
                    int pr = x;
                    for(int i=(int)history.size()-1; i>=0; i--){
                        par[history[i]] = pr, dist[history[i]] = dist[pr] + delay[history[i]];
                        cycleNum[history[i]] = cycleNum[pr], cycleIdx[history[i]] = cycleIdx[pr];
                        pr = history[i];
                    }
                }
                break;
            }

            visited[x] = i;
            history.push_back(x);
            timeSum += delay[x], x = nxt[x];
        }
    }



    #ifdef TEST
    printf("Person info done\n");
    for(int i=1; i<=n; i++){
        printf("%d: ", i);
        if(inCycle[i]) printf("in cycle, %d - %dth, dist %lld\n", cycleNum[i], cycleIdx[i], cycleT[cycleNum[i]][cycleIdx[i]]);
        else printf("in tree, par %d, dist %lld\n", par[i], dist[i]);
    }
    #endif // TEST
}

vector<int> child[200002];
int depth[200002], LCADB[200002][20];

void dfs(int x){
    for(auto y: child[x]){
        depth[y] = depth[x] + 1, par[y] = LCADB[y][0] = x;
        dfs(y);
    }
}

void organizeTree(){
    for(int i=1; i<=n; i++){
        if(par[i]) child[par[i]].push_back(i);
    }
    for(int i=1; i<=n; i++){
        if(inCycle[i]) dfs(i);
    }
    for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
}

int appleTo[200002]; ll appleDelay[200002];

void getAppleInfo(){
    for(int i=1; i<=k; i++){
        appleTo[i] = findNxt(b[i]);
        appleDelay[i] = (b[i] - a[appleTo[i]] + L) % L;
    }

    #ifdef TEST
    puts("Apple info");
    for(int i=1; i<=k; i++) printf("%d: to %d, delay %lld\n", i, appleTo[i], appleDelay[i]);
    #endif // TEST
}

/// ���� �Է��ϴ� �κ�

struct Query{
    int idx, x; ll t;
    Query(){}
    Query(int idx, int x, ll t): idx(idx), x(x), t(t){}
};
vector<Query> queries[200002];

void inputQuery(){
    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        Query p;
        p.idx = i;
        scanf("%d %lld", &p.x, &p.t);
        queries[p.x].push_back(p);
    }
}

/// �� �Ʒ����� ������ ó���Ѵ�.

int getLCA(int x, int y){
    if(depth[x] > depth[y]) swap(x, y);
    for(int d=0; d<20; d++) if((depth[y]-depth[x])&(1<<d)) y = LCADB[y][d];
    if(x==y) return x;
    for(int d=19; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
    return par[x];
}

int kthParent(int x, int k){
    for(int d=0; d<20; d++) if((k>>d)&1) x = LCADB[x][d];
    return x;
}


struct MergeSortTree{
    vector<ll> tree[1<<19];

    void init(int i, int l, int r, ll *A){
        if(l==r){
            tree[i] = vector<ll> (1, A[l]);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        tree[i].resize(tree[i*2].size() + tree[i*2+1].size());
        merge(tree[i*2].begin(), tree[i*2].end(), tree[i*2+1].begin(), tree[i*2+1].end(), tree[i].begin());
    }

    ll query(int i, int l, int r, int s, int e, ll v){
        if(r<s || e<l) return 0;
        if(s<=l && r<=e){
            return upper_bound(tree[i].begin(), tree[i].end(), v) - tree[i].begin();
        }
        int m = (l+r)>>1;
        return query(i*2, l, m, s, e, v) + query(i*2+1, m+1, r, s, e, v);
    }
} mst;

vector<int> appleList[200002]; /// �� �������� �����ϴ� ��� ����
ll ans[200002];
int in[200002], out[200002], inCnt;
ll mstVal[200002];

void dfs1_search(int x){
    in[x] = inCnt + 1;
    for(auto p: appleList[x]){
        mstVal[++inCnt] = dist[x] + appleDelay[p];
    }
    for(auto y: child[x]){
        dfs1_search(y);
    }
    out[x] = inCnt;
}

void dfs1_answer(int x){
    if(!inCycle[x] && in[x] <= out[x]) for(Query &p: queries[x]){
        ans[p.idx] += mst.query(1, 1, inCnt, in[x], out[x], p.t + dist[p.x]);
    }
    for(auto p: child[x]){
        dfs1_answer(p);
    }
}

void solveCase1(int root){ /// Ʈ�� -> Ʈ���� �ذ��ϴ� �Լ�
    /// delay[i] + dist[i] <= t + dist[x]���� �����ϴٴ� ���� �̿���
    inCnt = 0;
    dfs1_search(root);
    if(!inCnt) return;
    mst.init(1, 1, inCnt, mstVal);
    dfs1_answer(root);
}

/// �� �Ʒ����� case 2

struct Fenwick{
    int n;
    ll tree[200002];

    void init(int _n){
        n = _n;
        for(int i=0; i<=n; i++) tree[i] = 0;
    }

    void add(int x, ll v){
        while(x<=n){
            tree[x] += v;
            x += x&-x;
        }
    }

    ll sum(int x){
        ll ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }

    ll sum(int l, int r){
        if(l>r) return 0;
        return sum(r) - sum(l-1);
    }
} fenwick;

struct lazySegmentTree{
    ll sum[1<<19], lazy[1<<19];
    ll cnt[1<<19];

    void init(int i, int l, int r){
        sum[i] = lazy[i] = cnt[i] = 0;
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
    }

    void propagate(int i, int l, int r){
        sum[i] += lazy[i] * cnt[i];
        if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
        lazy[i] = 0;
    }

    void update(int i, int l, int r, int x){
        propagate(i, l, r);
        if(l==r){
            sum[i]++, cnt[i]++;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x), propagate(i*2+1, m+1, r);
        else update(i*2+1, m+1, r, x), propagate(i*2, l, m);
        sum[i] = sum[i*2] + sum[i*2+1], cnt[i] = cnt[i*2] + cnt[i*2+1];
    }

    void update(int i, int l, int r, int s, int e, ll v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] = v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, v);
        update(i*2+1, m+1, r, s, e, v);
        sum[i] = sum[i*2] + sum[i*2+1], cnt[i] = cnt[i*2] + cnt[i*2+1];
    }

    ll query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return 0;
        if(s<=l && r<=e) return sum[i];
        int m = (l+r)>>1;
        return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
    }
} segtree;

struct Event{
    int type; /// 0�̸� �� ����, 1�̸� ����
    ll val;
    int idx;
    Event(int type, ll val, int idx): type(type), val(val), idx(idx){}
    bool operator<(const Event &r)const{
        if(val != r.val) return val < r.val;
        else return type < r.type;
    }
};

vector<ll> puttingNumber[200002];

void solveCase2(int g){ /// ����Ŭ -> ����Ŭ�� �ذ��ϴ� �Լ�
    int s = (int)cycle[g].size();
    const ll MOD = cycleLength[g];

    for(int i=0; i<=s; i++) puttingNumber[i].clear();

    /// ���� ���������� ���� �� �κп� ���ؼ��� �غ�
    /// ����� ���� �������� ��� ����
    {
        vector<ll> renumber(1, -1e18);
        for(int i=1; i<s; i++){
            int x = cycle[g][i];
            for(int p: appleList[x]){
                ll v = appleDelay[p] - cycleT[g][i];
                puttingNumber[i].push_back(v);
                renumber.push_back(v);
            }
        }
        sort(renumber.begin(), renumber.end());
        renumber.erase(unique(renumber.begin(), renumber.end()), renumber.end());
        int r = (int)renumber.size() - 1;

        fenwick.init(r);
        for(int i=1; i<s; i++){
            for(ll p: puttingNumber[i]){
                int idx = lower_bound(renumber.begin(), renumber.end(), p) - renumber.begin();
                fenwick.add(idx, 1);
            }
            for(Query p: queries[cycle[g][i]]){
                int idx = upper_bound(renumber.begin(), renumber.end(), p.t - cycleT[g][i]) - renumber.begin() - 1;
                ans[p.idx] += fenwick.sum(1, idx);
            }
        }
    }

    /// �״��� ������������ ���� �ð��� ��� �����
    vector<ll> renumber;
    vector<Event> timeline;
    for(int i=0; i<s; i++){
        int x = cycle[g][i];
        for(int p: appleList[x]){
            ll v = appleDelay[p] + (i == 0 ? 0 : cycleLength[g] - cycleT[g][i]);
            renumber.push_back(v % MOD);
            timeline.push_back(Event(0, v, 0));
        }
        for(Query p: queries[x]){
            ll v = p.t - (i == 0 ? 0 : cycleT[g][i]);
            if(v<0) continue;
            timeline.push_back(Event(1, v, p.idx));
            renumber.push_back(v % MOD);
        }
    }
    sort(renumber.begin(), renumber.end());
    renumber.erase(unique(renumber.begin(), renumber.end()), renumber.end());
    sort(timeline.begin(), timeline.end());

    int r = (int)renumber.size();
    if(!r) return;
    segtree.init(1, 0, r-1);
    ll lastT = 0;
    for(Event p: timeline){
        if(lastT != p.val){ /// �ð��� ������Ʈ
            ll a1 = lastT / cycleLength[g], b1 = lastT % MOD;
            ll a2 = p.val / cycleLength[g], b2 = p.val % MOD;
            int idx1 = lower_bound(renumber.begin(), renumber.end(), b1) - renumber.begin() + 1;
            int idx2 = lower_bound(renumber.begin(), renumber.end(), b2) - renumber.begin();

            if(a1 == a2){
                segtree.update(1, 0, r-1, idx1, idx2, 1);
            }
            else{
                segtree.update(1, 0, r-1, idx1, r-1, 1);
                if(a2-a1>1) segtree.update(1, 0, r-1, 0, r-1, a2-a1-1);
                segtree.update(1, 0, r-1, 0, idx2, 1);
            }

            lastT = p.val;
        }
        int idx = lower_bound(renumber.begin(), renumber.end(), p.val%cycleLength[g]) - renumber.begin();
        if(p.type == 0){ /// �߰�
            segtree.update(1, 0, r-1, idx);
        }
        else{ /// ����
            ans[p.idx] += segtree.query(1, 0, r-1, 0, r-1);
        }
    }
}

void solve(){ /// ������ ó���ϴ� �Լ�
    /// �� ���� �ʱ�ȭ
    for(int i=1; i<=k; i++){
        int x = appleTo[i];
        appleList[x].push_back(i);
    }

    /// Session 1. Ʈ�� -> Ʈ��
    for(int i=1; i<=n; i++){
        if(inCycle[i] && !child[i].empty()) solveCase1(i);
    }

    /// Ʈ�� ������ ����Ŭ�� �Ѱ���
    for(int i=1; i<=k; i++){
        int x = appleTo[i];
        if(inCycle[x]) continue;
        appleDelay[i] += dist[x], x = cycle[cycleNum[x]][cycleIdx[x]];
        appleList[x].push_back(i);
    }

    /// Session 2. ����Ŭ -> ����Ŭ
    for(int i=1; i<=n; i++){
        if(inCycle[i] && cycleIdx[i] == 0) solveCase2(i);
    }
}

void output(){
    for(int i=1; i<=q; i++){
        printf("%lld\n", ans[i]);
    }
}

Compilation message

harvest.cpp: In function 'void input()':
harvest.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d %d %lld %lld", &n, &k, &L, &C);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:30:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
harvest.cpp:31:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     for(int i=1; i<=k; i++) scanf("%lld", &b[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
harvest.cpp: In function 'void inputQuery()':
harvest.cpp:156:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
harvest.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         scanf("%d %lld", &p.x, &p.t);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41332 KB Output is correct
2 Correct 22 ms 41680 KB Output is correct
3 Correct 25 ms 42364 KB Output is correct
4 Correct 29 ms 42312 KB Output is correct
5 Correct 27 ms 42896 KB Output is correct
6 Correct 27 ms 43008 KB Output is correct
7 Correct 27 ms 43092 KB Output is correct
8 Correct 28 ms 42448 KB Output is correct
9 Correct 27 ms 42428 KB Output is correct
10 Correct 26 ms 42416 KB Output is correct
11 Correct 26 ms 42424 KB Output is correct
12 Correct 27 ms 42012 KB Output is correct
13 Correct 34 ms 42448 KB Output is correct
14 Correct 28 ms 42012 KB Output is correct
15 Correct 27 ms 42836 KB Output is correct
16 Correct 32 ms 42776 KB Output is correct
17 Correct 28 ms 42736 KB Output is correct
18 Correct 26 ms 42748 KB Output is correct
19 Correct 28 ms 42820 KB Output is correct
20 Correct 28 ms 42848 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 60200 KB Output is correct
2 Correct 219 ms 81804 KB Output is correct
3 Correct 202 ms 85624 KB Output is correct
4 Correct 421 ms 103632 KB Output is correct
5 Correct 230 ms 118080 KB Output is correct
6 Correct 237 ms 118040 KB Output is correct
7 Correct 184 ms 77576 KB Output is correct
8 Correct 179 ms 77660 KB Output is correct
9 Correct 475 ms 94268 KB Output is correct
10 Correct 408 ms 92028 KB Output is correct
11 Correct 467 ms 94252 KB Output is correct
12 Correct 448 ms 94248 KB Output is correct
13 Correct 470 ms 94260 KB Output is correct
14 Correct 400 ms 91936 KB Output is correct
15 Correct 454 ms 85304 KB Output is correct
16 Correct 250 ms 99908 KB Output is correct
17 Correct 207 ms 99688 KB Output is correct
18 Correct 141 ms 61300 KB Output is correct
19 Correct 144 ms 61256 KB Output is correct
20 Correct 197 ms 80708 KB Output is correct

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41332 KB Output is correct
2 Correct 22 ms 41680 KB Output is correct
3 Correct 25 ms 42364 KB Output is correct
4 Correct 29 ms 42312 KB Output is correct
5 Correct 27 ms 42896 KB Output is correct
6 Correct 27 ms 43008 KB Output is correct
7 Correct 27 ms 43092 KB Output is correct
8 Correct 28 ms 42448 KB Output is correct
9 Correct 27 ms 42428 KB Output is correct
10 Correct 26 ms 42416 KB Output is correct
11 Correct 26 ms 42424 KB Output is correct
12 Correct 27 ms 42012 KB Output is correct
13 Correct 34 ms 42448 KB Output is correct
14 Correct 28 ms 42012 KB Output is correct
15 Correct 27 ms 42836 KB Output is correct
16 Correct 32 ms 42776 KB Output is correct
17 Correct 28 ms 42736 KB Output is correct
18 Correct 26 ms 42748 KB Output is correct
19 Correct 28 ms 42820 KB Output is correct
20 Correct 28 ms 42848 KB Output is correct
21 Correct 304 ms 60200 KB Output is correct
22 Correct 219 ms 81804 KB Output is correct
23 Correct 202 ms 85624 KB Output is correct
24 Correct 421 ms 103632 KB Output is correct
25 Correct 230 ms 118080 KB Output is correct
26 Correct 237 ms 118040 KB Output is correct
27 Correct 184 ms 77576 KB Output is correct
28 Correct 179 ms 77660 KB Output is correct
29 Correct 475 ms 94268 KB Output is correct
30 Correct 408 ms 92028 KB Output is correct
31 Correct 467 ms 94252 KB Output is correct
32 Correct 448 ms 94248 KB Output is correct
33 Correct 470 ms 94260 KB Output is correct
34 Correct 400 ms 91936 KB Output is correct
35 Correct 454 ms 85304 KB Output is correct
36 Correct 250 ms 99908 KB Output is correct
37 Correct 207 ms 99688 KB Output is correct
38 Correct 141 ms 61300 KB Output is correct
39 Correct 144 ms 61256 KB Output is correct
40 Correct 197 ms 80708 KB Output is correct
41 Correct 503 ms 127404 KB Output is correct
42 Correct 308 ms 91672 KB Output is correct
43 Correct 296 ms 102788 KB Output is correct
44 Incorrect 472 ms 119300 KB Output isn't correct
45 Halted 0 ms 0 KB -