oj.uz

Submission #799901

# Submission time Handle Problem Language Result Execution time Memory
799901 2023-08-01T08:00:17 Z 반딧불(#10081) Harvest (JOI20_harvest) C++17
0 / 100
 306 ms 80236 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];
    int 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];

    /// ���� ���������� ���� �� �κп� ���ؼ��� �غ�
    /// ����� ���� �������� ��� ����
    {
        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]; ll y = appleDelay[i];
        if(inCycle[x]) continue;
        y += 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 41392 KB Output is correct
2 Correct 24 ms 41732 KB Output is correct
3 Correct 27 ms 42400 KB Output is correct
4 Incorrect 27 ms 42340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 59292 KB Output is correct
2 Incorrect 206 ms 80236 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 41392 KB Output is correct
2 Correct 24 ms 41732 KB Output is correct
3 Correct 27 ms 42400 KB Output is correct
4 Incorrect 27 ms 42340 KB Output isn't correct
5 Halted 0 ms 0 KB -