oj.uz

Submission #799907

# Submission time Handle Problem Language Result Execution time Memory
799907 2023-08-01T08:05:13 Z 반딧불(#10081) Harvest (JOI20_harvest) C++17
0 / 100
 507 ms 123116 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];
        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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 41356 KB Output is correct
2 Correct 30 ms 41732 KB Output is correct
3 Correct 33 ms 42364 KB Output is correct
4 Correct 31 ms 42348 KB Output is correct
5 Correct 32 ms 43056 KB Output is correct
6 Correct 28 ms 43000 KB Output is correct
7 Correct 28 ms 42976 KB Output is correct
8 Correct 29 ms 42404 KB Output is correct
9 Correct 27 ms 42376 KB Output is correct
10 Correct 29 ms 42452 KB Output is correct
11 Correct 30 ms 42372 KB Output is correct
12 Correct 32 ms 41980 KB Output is correct
13 Correct 34 ms 42360 KB Output is correct
14 Incorrect 28 ms 42000 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 60196 KB Output is correct
2 Correct 203 ms 81352 KB Output is correct
3 Correct 231 ms 90584 KB Output is correct
4 Correct 454 ms 106712 KB Output is correct
5 Correct 245 ms 123116 KB Output is correct
6 Correct 266 ms 123000 KB Output is correct
7 Correct 170 ms 82608 KB Output is correct
8 Correct 157 ms 82640 KB Output is correct
9 Correct 468 ms 97324 KB Output is correct
10 Correct 421 ms 94896 KB Output is correct
11 Correct 475 ms 97184 KB Output is correct
12 Correct 507 ms 97248 KB Output is correct
13 Correct 423 ms 97260 KB Output is correct
14 Correct 368 ms 94904 KB Output is correct
15 Incorrect 440 ms 89368 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 41356 KB Output is correct
2 Correct 30 ms 41732 KB Output is correct
3 Correct 33 ms 42364 KB Output is correct
4 Correct 31 ms 42348 KB Output is correct
5 Correct 32 ms 43056 KB Output is correct
6 Correct 28 ms 43000 KB Output is correct
7 Correct 28 ms 42976 KB Output is correct
8 Correct 29 ms 42404 KB Output is correct
9 Correct 27 ms 42376 KB Output is correct
10 Correct 29 ms 42452 KB Output is correct
11 Correct 30 ms 42372 KB Output is correct
12 Correct 32 ms 41980 KB Output is correct
13 Correct 34 ms 42360 KB Output is correct
14 Incorrect 28 ms 42000 KB Output isn't correct
15 Halted 0 ms 0 KB -