oj.uz

Submission #799969

# Submission time Handle Problem Language Result Execution time Memory
799969 2023-08-01T08:57:28 Z 반딧불(#10081) Harvest (JOI20_harvest) C++17
25 / 100
 451 ms 130476 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];

    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 23 ms 41352 KB Output is correct
2 Correct 22 ms 41804 KB Output is correct
3 Correct 24 ms 42336 KB Output is correct
4 Correct 24 ms 42372 KB Output is correct
5 Correct 25 ms 42988 KB Output is correct
6 Correct 25 ms 42996 KB Output is correct
7 Correct 24 ms 43024 KB Output is correct
8 Correct 23 ms 42388 KB Output is correct
9 Correct 26 ms 42408 KB Output is correct
10 Correct 23 ms 42372 KB Output is correct
11 Correct 24 ms 42376 KB Output is correct
12 Correct 24 ms 41980 KB Output is correct
13 Correct 26 ms 42388 KB Output is correct
14 Correct 28 ms 42024 KB Output is correct
15 Correct 24 ms 42708 KB Output is correct
16 Correct 27 ms 42820 KB Output is correct
17 Correct 24 ms 42708 KB Output is correct
18 Correct 24 ms 42712 KB Output is correct
19 Correct 23 ms 42660 KB Output is correct
20 Correct 23 ms 42676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 59044 KB Output is correct
2 Correct 226 ms 80692 KB Output is correct
3 Correct 209 ms 86784 KB Output is correct
4 Correct 416 ms 102780 KB Output is correct
5 Correct 222 ms 119272 KB Output is correct
6 Correct 205 ms 119172 KB Output is correct
7 Correct 162 ms 78752 KB Output is correct
8 Correct 152 ms 78692 KB Output is correct
9 Correct 423 ms 93456 KB Output is correct
10 Correct 378 ms 91156 KB Output is correct
11 Correct 415 ms 93356 KB Output is correct
12 Correct 432 ms 93356 KB Output is correct
13 Correct 436 ms 93472 KB Output is correct
14 Correct 373 ms 91212 KB Output is correct
15 Correct 432 ms 85528 KB Output is correct
16 Correct 216 ms 105352 KB Output is correct
17 Correct 203 ms 105096 KB Output is correct
18 Correct 124 ms 66004 KB Output is correct
19 Correct 115 ms 65908 KB Output is correct
20 Correct 177 ms 86340 KB Output is correct

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 41352 KB Output is correct
2 Correct 22 ms 41804 KB Output is correct
3 Correct 24 ms 42336 KB Output is correct
4 Correct 24 ms 42372 KB Output is correct
5 Correct 25 ms 42988 KB Output is correct
6 Correct 25 ms 42996 KB Output is correct
7 Correct 24 ms 43024 KB Output is correct
8 Correct 23 ms 42388 KB Output is correct
9 Correct 26 ms 42408 KB Output is correct
10 Correct 23 ms 42372 KB Output is correct
11 Correct 24 ms 42376 KB Output is correct
12 Correct 24 ms 41980 KB Output is correct
13 Correct 26 ms 42388 KB Output is correct
14 Correct 28 ms 42024 KB Output is correct
15 Correct 24 ms 42708 KB Output is correct
16 Correct 27 ms 42820 KB Output is correct
17 Correct 24 ms 42708 KB Output is correct
18 Correct 24 ms 42712 KB Output is correct
19 Correct 23 ms 42660 KB Output is correct
20 Correct 23 ms 42676 KB Output is correct
21 Correct 285 ms 59044 KB Output is correct
22 Correct 226 ms 80692 KB Output is correct
23 Correct 209 ms 86784 KB Output is correct
24 Correct 416 ms 102780 KB Output is correct
25 Correct 222 ms 119272 KB Output is correct
26 Correct 205 ms 119172 KB Output is correct
27 Correct 162 ms 78752 KB Output is correct
28 Correct 152 ms 78692 KB Output is correct
29 Correct 423 ms 93456 KB Output is correct
30 Correct 378 ms 91156 KB Output is correct
31 Correct 415 ms 93356 KB Output is correct
32 Correct 432 ms 93356 KB Output is correct
33 Correct 436 ms 93472 KB Output is correct
34 Correct 373 ms 91212 KB Output is correct
35 Correct 432 ms 85528 KB Output is correct
36 Correct 216 ms 105352 KB Output is correct
37 Correct 203 ms 105096 KB Output is correct
38 Correct 124 ms 66004 KB Output is correct
39 Correct 115 ms 65908 KB Output is correct
40 Correct 177 ms 86340 KB Output is correct
41 Correct 451 ms 130476 KB Output is correct
42 Correct 279 ms 96500 KB Output is correct
43 Correct 262 ms 104848 KB Output is correct
44 Incorrect 440 ms 120072 KB Output isn't correct
45 Halted 0 ms 0 KB -