oj.uz

Submission #1038736

# Submission time Handle Problem Language Result Execution time Memory
1038736 2024-07-30T07:05:10 Z 김은성(#10985) Tower (JOI24_tower) C++17
0 / 100
 2000 ms 66132 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[4009][2009], l[200009], r[200009], basic[200009];
int main(){
    int n, t, i, j=0, k;
    ll d, a, b;
    scanf("%d %d", &n, &t);
    scanf("%lld %lld %lld", &d, &a, &b);
    for(i=1; i<=n; i++){
        scanf("%lld %lld", &l[i], &r[i]);
        l[i]--;
        r[i]++;
    }
    l[n+1] = (ll)1e16;
    if(b > a*d){
        dp[0][0] = 0;
        for(i=1; i<=n; i++)
            dp[0][i] = -1;
        for(k=1; k<=n; k++){
            j = 0;
            deque<int> q;
            dp[k][0] = -1;
            for(i=1; i<=n; i++){
                if(dp[k-1][i-1] != -1)
                    q.push_back(i-1);
                while(l[j+1] < r[i] - d){
                    if(q.front() == j)
                        q.pop_front();
                    j++;
                }
                if(q.empty())
                    dp[k][i] = -1;
                else{
                    dp[k][i] = max(dp[k-1][q.front()] + d, r[i]);
                    if(dp[k][i] > l[i+1])
                        dp[k][i] = -1;
                }
            }
        }
        for(i=1; i<=t; i++){
            ll x;
            scanf("%lld", &x);
            int idx = lower_bound(l+1, l+n+1, x) - l;
            idx--;
            for(j=0; j<=n; j++){
                if(dp[j][idx] == -1 || dp[j][idx] > x)
                    continue;
                printf("%lld\n", x + j * (b-a*d));
                break;
            }
            if(j==n+1)
                printf("-1\n");
        }
    }
    else{
        dp[0][0] = 0;
        for(i=1; i<=n; i++)
            dp[0][i] = -1;
        for(k=1; k<=2*n+4; k++){
            j = 0;
            deque<int> q;
            dp[k][0] = (l[1] >= d ? l[1] : -1);
            for(i=1; i<=n; i++){
                if(dp[k-1][i-1] != -1)
                    q.push_back(i-1);
                while(l[j+1] < r[i] - d){
                    if(q.front() == j)
                        q.pop_front();
                    j++;
                }
                if(q.empty())
                    dp[k][i] = -1;
                else{
                    dp[k][i] = max(dp[k-1][q.front()] + d, r[i]);
                    if(dp[k][i] > l[i+1])
                        dp[k][i] = -1;
                }
               if(k >= 2){
                    if(dp[k-2][i-1] == -1 || l[i]-r[i-1] < d)
                        continue;
                    ll delta = (l[i] - r[i-1]) % d;
                    if(dp[k-2][i-1] - r[i-1] <= delta){
                        ll temp = l[i] - (delta - (dp[k-2][i-1] - r[i-1])) + d;
                        if(temp >= r[i] && temp <= l[i+1]){
                            if(dp[k][i] == -1 || dp[k][i] > temp)
                                dp[k][i] = temp;
                        }
                    }
                }
            }
        }
        basic[0] = 0;
        for(i=1; i<=n; i++)
            basic[i] = basic[i-1] + max((r[i]-l[i-1])/d - 1, 0ll);
        for(i=1; i<=t; i++){
            ll x;
            scanf("%lld", &x);
            //printf("i=%d t=%d x=%lld\n", i,t,  x);
            int idx = lower_bound(l+1, l+n+1, x) - l;
            idx--;
            for(j=2*n+4; j>=0; j--){
                if(dp[j][idx] == -1 || dp[j][idx] > x)
                    continue;
                printf("%lld\n", x + (j+basic[idx] + (x-dp[j][idx])/d) * (b-a*d));
                break;
            }
            if(j==-1)
                printf("-1\n");
        }
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     scanf("%d %d", &n, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%lld %lld %lld", &d, &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         scanf("%lld %lld", &l[i], &r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:43:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |             scanf("%lld", &x);
      |             ~~~~~^~~~~~~~~~~~
Main.cpp:98:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |             scanf("%lld", &x);
      |             ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 38.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7536 KB Output is correct
2 Correct 28 ms 8792 KB Output is correct
3 Correct 58 ms 66132 KB Output is correct
4 Execution timed out 2068 ms 34132 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

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