oj.uz

Submission #260966

# Submission time Handle Problem Language Result Execution time Memory
260966 2020-08-11T08:49:36 Z 반딧불(#5074) Harvest (JOI20_harvest) C++17
0 / 100
 5000 ms 20708 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int x; ll y, val;
    dat(){}
    dat(int x, ll y, ll val): x(x), y(y), val(val){}

    bool operator<(const dat &r)const{
        return y<r.y;
    }
};

int n, m;
ll l, c;
int q;
ll a[200002], b[200002];
int link[200002];
vector<int> reverseLink[200002];

ll DP[200002];
int start[200002];
int isStart[200002];
ll startTime[200002];

vector<dat> query[200002];
vector<ll> cycleStart[200002];
int visited[200002];
bool isCycle[200002];
ll ans[200002];
ll cycleLength[200002];

int dfs1(int x){
    if(visited[x] == 2) return 0;
    if(visited[x] == 1){
        isCycle[x] = 1;
        return x;
    }

    visited[x] = 1;
    int tmp = dfs1(link[x]);
    if(tmp == x) tmp = 0;
    else if(tmp) isCycle[x] = 1;
    visited[x] = 2;
    return tmp;
}

ll dfs2(int x, ll t){
    if(isCycle[x]){
        if(visited[x]){
            cycleLength[x] = t - DP[x];
            return cycleLength[x];
        }

        DP[x] = t;

        visited[x] = 1;
        cycleStart[x].push_back(t);

        ll dist = a[link[x]] - a[x] + c/l*l;
        while(dist < c) dist += l;

        cycleLength[x] = dfs2(link[x], t+dist);
        return cycleLength[x];
    }

    DP[x] = t;

    if(!query[x].empty()){
        auto it = lower_bound(query[x].begin(), query[x].end(), dat(0, t, 0));
        it->val++;
    }

    ll dist = a[link[x]] - a[x] + c/l*l;
    while(dist < c) dist += l;

    dfs2(link[x], t+dist);
}

int main(){
    scanf("%d %d %lld %lld", &n, &m, &l, &c);
    for(int i=1; i<=n; i++){
        scanf("%lld", &a[i]);
        a[i] = l - 1 - a[i];
    }
    for(int i=1; i<=m; i++){
        scanf("%lld", &b[i]);
        b[i] = l - 1 - b[i];
    }
    sort(a+1, a+n+1);
    sort(b+1, b+m+1);

    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        int x; ll y;
        scanf("%d %lld", &x, &y);
        x = n + 1 - x;
        query[x].push_back(dat(i, y, 0));
    }

    for(int i=1; i<=n; i++){
        link[i] = lower_bound(a+1, a+n+1, a[i] + c%l) - a;
        if(link[i] == n+1) link[i] = lower_bound(a+1, a+n+1, a[i] + c%l - l) - a;

        reverseLink[link[i]].push_back(i);
        sort(query[i].begin(), query[i].end());
    }

    for(int i=1; i<=n; i++) dfs1(i);

    for(int i=1; i<=m; i++){
        start[i] = lower_bound(a+1, a+n+1, b[i]) - a;
        if(start[i] == n+1) start[i] = 1;
        isStart[start[i]]++;

        startTime[i] = a[start[i]] - b[i];
        if(startTime[i] < 0) startTime[i] += l;
    }

    for(int i=1; i<=m; i++){
        memset(visited, 0, sizeof(visited));
        dfs2(start[i], startTime[i]);
    }

    for(int i=1; i<=n; i++){
        ll sum = 0;
        for(auto &x: query[i]){
            x.val += sum;
            sum = x.val;
        }
    }

    for(int i=1; i<=n; i++){
        for(auto &x: cycleStart[i]){
            for(auto &y: query[i]){
                if(x > y.y) continue;
                y.val += (y.y - x) / cycleLength[i] + 1;
            }
        }
    }

    for(int i=1; i<=n; i++){
        for(auto &y: query[i]) ans[y.x] = y.val;
    }
    for(int i=1; i<=q; i++){
        printf("%lld\n", ans[i]);
    }
}

Compilation message

harvest.cpp: In function 'll dfs2(int, ll)':
harvest.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
harvest.cpp: In function 'int main()':
harvest.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %lld %lld", &n, &m, &l, &c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &a[i]);
         ~~~~~^~~~~~~~~~~~~~~
harvest.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &b[i]);
         ~~~~~^~~~~~~~~~~~~~~
harvest.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
harvest.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %lld", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15488 KB Output is correct
2 Correct 102 ms 15740 KB Output is correct
3 Correct 200 ms 15608 KB Output is correct
4 Incorrect 115 ms 17528 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5074 ms 20708 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15488 KB Output is correct
2 Correct 102 ms 15740 KB Output is correct
3 Correct 200 ms 15608 KB Output is correct
4 Incorrect 115 ms 17528 KB Output isn't correct
5 Halted 0 ms 0 KB -