oj.uz

Submission #528567

# Submission time Handle Problem Language Result Execution time Memory
528567 2022-02-20T15:21:28 Z mhy908 Railway Trip 2 (JOI22_ho_t4) C++14
11 / 100
 992 ms 56844 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]=*ms.rbegin();
        if(i>=k){
            for(auto j:vcl[i-k+1])ms.erase(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]=*ms.begin();
        if(i<=n-k+1){
            for(auto j:vcr[i+k-1])ms.erase(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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 4 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 4 ms 5320 KB Output is correct
7 Correct 4 ms 5324 KB Output is correct
8 Incorrect 4 ms 5196 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 4 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 4 ms 5320 KB Output is correct
7 Correct 4 ms 5324 KB Output is correct
8 Incorrect 4 ms 5196 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 47380 KB Output is correct
2 Correct 674 ms 47240 KB Output is correct
3 Correct 717 ms 48112 KB Output is correct
4 Correct 660 ms 47176 KB Output is correct
5 Correct 518 ms 50800 KB Output is correct
6 Correct 696 ms 51040 KB Output is correct
7 Correct 497 ms 55820 KB Output is correct
8 Correct 447 ms 48740 KB Output is correct
9 Correct 465 ms 49612 KB Output is correct
10 Correct 675 ms 48836 KB Output is correct
11 Correct 659 ms 53572 KB Output is correct

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 879 ms 50816 KB Output is correct
2 Correct 992 ms 48288 KB Output is correct
3 Correct 955 ms 46668 KB Output is correct
4 Correct 939 ms 45764 KB Output is correct
5 Correct 819 ms 45176 KB Output is correct
6 Correct 832 ms 45124 KB Output is correct
7 Correct 709 ms 52752 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 14 ms 5820 KB Output is correct
10 Correct 703 ms 51240 KB Output is correct
11 Correct 784 ms 56844 KB Output is correct
12 Correct 825 ms 50688 KB Output is correct
13 Correct 824 ms 55428 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Incorrect 15 ms 5752 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 4 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 4 ms 5320 KB Output is correct
7 Correct 4 ms 5324 KB Output is correct
8 Incorrect 4 ms 5196 KB Output isn't correct
9 Halted 0 ms 0 KB -