oj.uz

답안 #528572

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
528572 2022-02-20T15:26:25 Z mhy908 Railway Trip 2 (JOI22_ho_t4) C++14
100 / 100
 1082 ms 57308 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;

int n, k, m, q, l[100010], r[100010];
multiset<int> ms;
vector<int> vcl[100010], vcr[100010];

struct SEG{
    pii tree[400010];
    pii func(pii a, pii b){return mp(min(a.F, b.F), max(a.S, b.S));}
    void upd(int point, int s, int e, int num, pii val){
        if(s==e){
            tree[point]=val;
            return;
        }
        if(num<=(s+e)/2)upd(point*2, s, (s+e)/2, num, val);
        else upd(point*2+1, (s+e)/2+1, e, num, val);
        tree[point]=func(tree[point*2], tree[point*2+1]);
    }
    pii query(int point, int s, int e, int a, int b){
        if(e<a||s>b)return mp(INF, 0);
        if(a<=s&&e<=b)return tree[point];
        return func(query(point*2, s, (s+e)/2, a, b), query(point*2+1, (s+e)/2+1, e, a, b));
    }
}seg[19];

int main(){
    scanf("%d %d %d", &n, &k, &m);
    for(int i=1; i<=m; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        if(a<b)vcl[a].eb(b);
        else vcr[a].eb(b);
    }
    for(int i=1; i<=n; i++){
        for(auto j:vcl[i])ms.insert(j);
        r[i]=i;
        if(ms.size())r[i]=max(r[i], *ms.rbegin());
        if(i>=k){
            for(auto j:vcl[i-k+1])ms.erase(ms.find(j));
        }
    }
    ms.clear();
    for(int i=n; i>=1; i--){
        for(auto j:vcr[i])ms.insert(j);
        l[i]=i;
        if(ms.size())l[i]=min(l[i], *ms.begin());
        if(i<=n-k+1){
            for(auto j:vcr[i+k-1])ms.erase(ms.find(j));
        }
    }
    for(int i=1; i<=n; i++)seg[0].upd(1, 1, n, i, mp(l[i], r[i]));
    for(int i=1; i<=18; i++){
        for(int j=1; j<=n; j++){
            pii tmp=seg[i-1].query(1, 1, n, j, j);
            seg[i].upd(1, 1, n, j, seg[i-1].query(1, 1, n, tmp.F, tmp.S));
        }
    }
    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        int a, b, ans=0;
        scanf("%d %d", &a, &b);
        pii r=mp(a, a);
        for(int j=18; j>=0; j--){
            pii r2=seg[j].query(1, 1, n, r.F, r.S);
            if(b<r2.F||b>r2.S)r=r2, ans+=(1<<j);
        }
        if(ans>n)puts("-1");
        else printf("%d\n", ans+1);
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d %d %d", &n, &k, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
Main.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5196 KB Output is correct
2 Correct 5 ms 5196 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 3 ms 5324 KB Output is correct
7 Correct 4 ms 5324 KB Output is correct
8 Correct 3 ms 5324 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 3 ms 5068 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 5 ms 5248 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5196 KB Output is correct
2 Correct 5 ms 5196 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 3 ms 5324 KB Output is correct
7 Correct 4 ms 5324 KB Output is correct
8 Correct 3 ms 5324 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 3 ms 5068 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 5 ms 5248 KB Output is correct
13 Correct 19 ms 5836 KB Output is correct
14 Correct 21 ms 5820 KB Output is correct
15 Correct 12 ms 5776 KB Output is correct
16 Correct 12 ms 5884 KB Output is correct
17 Correct 16 ms 5836 KB Output is correct
18 Correct 12 ms 5836 KB Output is correct
19 Correct 13 ms 5836 KB Output is correct
20 Correct 12 ms 5856 KB Output is correct
21 Correct 9 ms 5852 KB Output is correct
22 Correct 15 ms 5876 KB Output is correct
23 Correct 19 ms 5836 KB Output is correct
24 Correct 16 ms 5836 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 875 ms 47364 KB Output is correct
2 Correct 785 ms 47348 KB Output is correct
3 Correct 811 ms 47844 KB Output is correct
4 Correct 674 ms 47180 KB Output is correct
5 Correct 531 ms 50756 KB Output is correct
6 Correct 726 ms 51016 KB Output is correct
7 Correct 560 ms 55816 KB Output is correct
8 Correct 519 ms 48740 KB Output is correct
9 Correct 467 ms 49524 KB Output is correct
10 Correct 678 ms 48836 KB Output is correct
11 Correct 719 ms 53488 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 852 ms 49948 KB Output is correct
2 Correct 805 ms 53248 KB Output is correct
3 Correct 984 ms 50528 KB Output is correct
4 Correct 623 ms 55808 KB Output is correct
5 Correct 642 ms 53312 KB Output is correct
6 Correct 626 ms 53188 KB Output is correct
7 Correct 891 ms 53720 KB Output is correct
8 Correct 910 ms 53796 KB Output is correct

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 903 ms 50780 KB Output is correct
2 Correct 1028 ms 48280 KB Output is correct
3 Correct 1043 ms 46764 KB Output is correct
4 Correct 1008 ms 45752 KB Output is correct
5 Correct 858 ms 45212 KB Output is correct
6 Correct 850 ms 45040 KB Output is correct
7 Correct 734 ms 52704 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 13 ms 5800 KB Output is correct
10 Correct 713 ms 51232 KB Output is correct
11 Correct 800 ms 56888 KB Output is correct
12 Correct 851 ms 50728 KB Output is correct
13 Correct 871 ms 55368 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 17 ms 5812 KB Output is correct
16 Correct 780 ms 47664 KB Output is correct
17 Correct 991 ms 57308 KB Output is correct
18 Correct 958 ms 47856 KB Output is correct
19 Correct 973 ms 47832 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5196 KB Output is correct
2 Correct 5 ms 5196 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 3 ms 5324 KB Output is correct
7 Correct 4 ms 5324 KB Output is correct
8 Correct 3 ms 5324 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 3 ms 5068 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 5 ms 5248 KB Output is correct
13 Correct 19 ms 5836 KB Output is correct
14 Correct 21 ms 5820 KB Output is correct
15 Correct 12 ms 5776 KB Output is correct
16 Correct 12 ms 5884 KB Output is correct
17 Correct 16 ms 5836 KB Output is correct
18 Correct 12 ms 5836 KB Output is correct
19 Correct 13 ms 5836 KB Output is correct
20 Correct 12 ms 5856 KB Output is correct
21 Correct 9 ms 5852 KB Output is correct
22 Correct 15 ms 5876 KB Output is correct
23 Correct 19 ms 5836 KB Output is correct
24 Correct 16 ms 5836 KB Output is correct
25 Correct 875 ms 47364 KB Output is correct
26 Correct 785 ms 47348 KB Output is correct
27 Correct 811 ms 47844 KB Output is correct
28 Correct 674 ms 47180 KB Output is correct
29 Correct 531 ms 50756 KB Output is correct
30 Correct 726 ms 51016 KB Output is correct
31 Correct 560 ms 55816 KB Output is correct
32 Correct 519 ms 48740 KB Output is correct
33 Correct 467 ms 49524 KB Output is correct
34 Correct 678 ms 48836 KB Output is correct
35 Correct 719 ms 53488 KB Output is correct
36 Correct 852 ms 49948 KB Output is correct
37 Correct 805 ms 53248 KB Output is correct
38 Correct 984 ms 50528 KB Output is correct
39 Correct 623 ms 55808 KB Output is correct
40 Correct 642 ms 53312 KB Output is correct
41 Correct 626 ms 53188 KB Output is correct
42 Correct 891 ms 53720 KB Output is correct
43 Correct 910 ms 53796 KB Output is correct
44 Correct 903 ms 50780 KB Output is correct
45 Correct 1028 ms 48280 KB Output is correct
46 Correct 1043 ms 46764 KB Output is correct
47 Correct 1008 ms 45752 KB Output is correct
48 Correct 858 ms 45212 KB Output is correct
49 Correct 850 ms 45040 KB Output is correct
50 Correct 734 ms 52704 KB Output is correct
51 Correct 5 ms 5196 KB Output is correct
52 Correct 13 ms 5800 KB Output is correct
53 Correct 713 ms 51232 KB Output is correct
54 Correct 800 ms 56888 KB Output is correct
55 Correct 851 ms 50728 KB Output is correct
56 Correct 871 ms 55368 KB Output is correct
57 Correct 4 ms 5196 KB Output is correct
58 Correct 17 ms 5812 KB Output is correct
59 Correct 780 ms 47664 KB Output is correct
60 Correct 991 ms 57308 KB Output is correct
61 Correct 958 ms 47856 KB Output is correct
62 Correct 973 ms 47832 KB Output is correct
63 Correct 989 ms 47356 KB Output is correct
64 Correct 1026 ms 47956 KB Output is correct
65 Correct 927 ms 47556 KB Output is correct
66 Correct 607 ms 53196 KB Output is correct
67 Correct 1020 ms 51528 KB Output is correct
68 Correct 854 ms 49072 KB Output is correct
69 Correct 645 ms 52256 KB Output is correct
70 Correct 890 ms 49060 KB Output is correct
71 Correct 1082 ms 49016 KB Output is correct