oj.uz

답안 #745685

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745685 2023-05-21T02:02:15 Z 반딧불(#9962) Double Attendance (CCO22_day1problem3) C++17
0 / 25
 6 ms 9736 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n[2], k;
pair<ll, ll> arr[2][300002];
vector<ll> pl[2], pr[2];
ll DP[2][600002];
int ans;

inline int idx(int d, ll t){
    return upper_bound(pl[d].begin(), pl[d].end(), t) - pl[d].begin();
}

inline bool inside(int d, ll t){
    int x = idx(d, t);
    return x && arr[d][x].first <= t && t <= arr[d][x].second;
}

inline int sum(int d, ll L, ll R){
//    printf("%d %lld %lld: %d %d\n", d, L, R, lower_bound(pl[d].begin(), pl[d].end(), R) - pl[d].begin(),
//           lower_bound(pr[d].begin(), pr[d].end(), L) - pr[d].begin());
    return (lower_bound(pl[d].begin(), pl[d].end(), R) - pl[d].begin())
         - (lower_bound(pr[d].begin(), pr[d].end(), L) - pr[d].begin());
}

int main(){
    scanf("%d %d %d", &n[0], &n[1], &k); k*=2;
    for(int d=0; d<=1; d++){
        for(int i=1; i<=n[d]; i++){
            scanf("%lld %lld", &arr[d][i].first, &arr[d][i].second);
            arr[d][i].first = arr[d][i].first * 2 + 1;
            arr[d][i].second = arr[d][i].second * 2 - 1;
            pl[d].push_back(arr[d][i].first);
            pr[d].push_back(arr[d][i].second);
        }
        sort(arr[d]+1, arr[d]+n[d]+1);
        sort(pl[d].begin(), pl[d].end());
        sort(pr[d].begin(), pr[d].end());
    }
    arr[0][n[0]+1] = arr[1][n[1]+1] = make_pair(ll(2e18), ll(2e18));
    for(int i=0; i<=1; i++) for(int j=0; j<=600000; j++) DP[i][j] = 1e18;
    DP[0][0] = 0;
    for(int i=0; i<=n[0]+n[1]; i++){
        /// ���ķ� ������
        for(int s=0; s<2; s++){
            for(int e=0; e<2; e++){
                if(s==e){ /// ���� �ٿ� �״��
                    DP[s][i+1] = min(DP[s][i+1], arr[s][idx(s, DP[s][i])+1].first);
                }
                else{
                    ll L = DP[s][i] + k;
                    ll R = L;
                    if(inside(s, DP[s][i])) R = max(R, arr[s][idx(s, DP[s][i])].second-k+1);
                    ll S = sum(e,L,R);
                    DP[e][i+S] = min(DP[e][i+S], R);
                }
            }
        }
//        printf("%d: %lld %lld\n", i, DP[0][i], DP[1][i]);
    }
    for(int i=0; i<=n[0]+n[1]; i++) if(DP[0][i] < 1e18 || DP[1][i] < 1e18) ans = i;
    printf("%d", ans);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d %d %d", &n[0], &n[1], &k); k*=2;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |             scanf("%lld %lld", &arr[d][i].first, &arr[d][i].second);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9660 KB Output is correct
2 Correct 6 ms 9664 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Incorrect 5 ms 9684 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9660 KB Output is correct
2 Correct 6 ms 9664 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Incorrect 5 ms 9684 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 6 ms 9736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9660 KB Output is correct
2 Correct 6 ms 9664 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Incorrect 5 ms 9684 KB Output isn't correct
7 Halted 0 ms 0 KB -