oj.uz

Submission #260903

# Submission time Handle Problem Language Result Execution time Memory
260903 2020-08-11T07:24:35 Z 반딧불(#5074) Harvest (JOI20_harvest) C++17
0 / 100
 5000 ms 21336 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, l, c, q;
int a[200002], b[200002];
int link[200002];
vector<int> reverseLink[200002];

int 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];

inline int rec(int x){
    if(x<0) return x+l;
    return x;
}

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) return 0;
    else if(tmp) isCycle[x] = 1;
    visited[x] = 2;
    return tmp;
}

void dfs2(int x, ll t){
    if(isCycle[x]){
        if(visited[x]) return;

        visited[x] = 1;
        cycleStart[x].push_back(t);
        dfs2(link[x], t+rec(a[link[x]] - a[x]));
        return;
    }

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

int main(){
    scanf("%d %d %d %d", &n, &m, &l, &c);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
        a[i] = l - 1 - a[i];
    }
    for(int i=1; i<=m; i++){
        scanf("%d", &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) - a;
        if(link[i] == n+1) link[i] = lower_bound(a+1, a+n+1, a[i] + c - 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) break;
                y.val += (y.y - x) / l + 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 'int main()':
harvest.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &n, &m, &l, &c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
harvest.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[i]);
         ~~~~~^~~~~~~~~~~~~
harvest.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
harvest.cpp:86: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 Incorrect 11 ms 15448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 15448 KB Output isn't correct
2 Halted 0 ms 0 KB -