oj.uz

Submission #528569

# Submission time Handle Problem Language Result Execution time Memory
528569 2022-02-20T15:22:47 Z mhy908 Railway Trip 2 (JOI22_ho_t4) C++14
46 / 100
 1022 ms 57304 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(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]=*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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5216 KB Output is correct
2 Correct 4 ms 5196 KB Output is correct
3 Correct 3 ms 5228 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 5 ms 5268 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 5 ms 5216 KB Output is correct
2 Correct 4 ms 5196 KB Output is correct
3 Correct 3 ms 5228 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 5 ms 5268 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 775 ms 47400 KB Output is correct
2 Correct 734 ms 47332 KB Output is correct
3 Correct 848 ms 47956 KB Output is correct
4 Correct 696 ms 47064 KB Output is correct
5 Correct 573 ms 50688 KB Output is correct
6 Correct 725 ms 51084 KB Output is correct
7 Correct 507 ms 55836 KB Output is correct
8 Correct 463 ms 48724 KB Output is correct
9 Correct 443 ms 49668 KB Output is correct
10 Correct 697 ms 48852 KB Output is correct
11 Correct 655 ms 53496 KB Output is correct

Subtask #4
0 / 25.0

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

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 886 ms 50780 KB Output is correct
2 Correct 1022 ms 48176 KB Output is correct
3 Correct 999 ms 46748 KB Output is correct
4 Correct 959 ms 45680 KB Output is correct
5 Correct 850 ms 45460 KB Output is correct
6 Correct 940 ms 45040 KB Output is correct
7 Correct 803 ms 52820 KB Output is correct
8 Correct 7 ms 5196 KB Output is correct
9 Correct 18 ms 5904 KB Output is correct
10 Correct 723 ms 51052 KB Output is correct
11 Correct 814 ms 56948 KB Output is correct
12 Correct 833 ms 50652 KB Output is correct
13 Correct 830 ms 55424 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 16 ms 5708 KB Output is correct
16 Correct 715 ms 47660 KB Output is correct
17 Correct 994 ms 57304 KB Output is correct
18 Correct 959 ms 47784 KB Output is correct
19 Correct 976 ms 47940 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5216 KB Output is correct
2 Correct 4 ms 5196 KB Output is correct
3 Correct 3 ms 5228 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 5 ms 5268 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 -