oj.uz

답안 #879099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
879099 2023-11-26T10:47:43 Z Piokemon Railway Trip 2 (JOI22_ho_t4) C++17
25 / 100
 1678 ms 44236 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int M = 2e5;
constexpr int K = 20;
constexpr int base = (1<<17);
pair<int,int> tree[2*base+9][K];
pair<int,int> lazy[2*base+9];

void daj(int x, int k){
    tree[2*x][k].first = min(tree[2*x][k].first,lazy[x].first); 
    tree[2*x][k].second = max(tree[2*x][k].second,lazy[x].second); 
    lazy[2*x].first = min(lazy[2*x].first,lazy[x].first); 
    lazy[2*x].second = max(lazy[2*x].second,lazy[x].second);

    tree[2*x+1][k].first = min(tree[2*x+1][k].first,lazy[x].first); 
    tree[2*x+1][k].second = max(tree[2*x+1][k].second,lazy[x].second); 
    lazy[2*x+1].first = min(lazy[2*x+1].first,lazy[x].first); 
    lazy[2*x+1].second = max(lazy[2*x+1].second,lazy[x].second); 

    lazy[x] = {1e9,-1e9};
}

void sed(int x, int l, int a, int b, int p, int k, pair<int,int> val){
    if (p<=a && b<=k){
        tree[x][l].first = min(tree[x][l].first,val.first);
        tree[x][l].second = max(tree[x][l].second,val.second);
        lazy[x].first = min(lazy[x].first,val.first);
        lazy[x].second = max(lazy[x].second,val.second);
        return;
    }
    if (b<p || a>k) return;
    daj(x,l);
    int mid=(a+b)/2;
    sed(2*x,l,a,mid,p,k,val);
    sed(2*x+1,l,mid+1,b,p,k,val);
    tree[x][l].first = min(tree[2*x][l].first,tree[2*x+1][l].first);
    tree[x][l].second = max(tree[2*x][l].second,tree[2*x+1][l].second);
}

pair<int,int> query(int x, int l, int a, int b, int p, int k){
    if (p<=a && b<=k) return tree[x][l];
    if (b<p || a>k) return {1e9,-1e9};
    int mid=(a+b)/2;
    if (l==0) daj(x,l);
    pair<int,int> j = query(2*x,l,a,mid,p,k);
    pair<int,int> d = query(2*x+1,l,mid+1,b,p,k);
    tree[x][l].first = min(tree[2*x][l].first,tree[2*x+1][l].first);
    tree[x][l].second = max(tree[2*x][l].second,tree[2*x+1][l].second);
    return {min(j.first,d.first),max(j.second,d.second)};
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,zas,m,a,b,q;
    cin >> n >> zas;
    cin >> m;
    for (int k=0;k<K;k++){
        for (int x=0;x<=2*base;x++) tree[x][k] = {1e9,-1e9};
    }
    for (int x=0;x<=2*base;x++) lazy[x] = {1e9,-1e9};
    for (int x=1;x<=n;x++) tree[x+base-1][0] = {x,x};
    for (int x=base-1;x>=1;x--){
            tree[x][0].first = min(tree[2*x][0].first,tree[2*x+1][0].second);
            tree[x][0].second = max(tree[2*x][0].first,tree[2*x+1][0].second);
        }
    for (int x=0;x<m;x++){
        cin >> a >> b;
        if (a<b) sed(1,0,1,base,a,min(a+zas-1,b-1),{1e9,b});
        if (a>b) sed(1,0,1,base,max(a-zas+1,b+1),a,{b,-1e9});
    }
    for (int x=0;x<=base;x++) daj(x,0);
    for (int k=1;k<K;k++){
        for (int x=1;x<=n;x++){
            tree[x+base-1][k] = query(1,k-1,1,base,tree[x+base-1][k-1].first,tree[x+base-1][k-1].second);
        }
        for (int x=base-1;x>=1;x--){
            tree[x][k].first = min(tree[2*x][k].first,tree[2*x+1][k].second);
            tree[x][k].second = max(tree[2*x][k].first,tree[2*x+1][k].second);
        }
    }
    for (int k=0;k<K;k++){
        for (int x=1;x<=n;x++){
            pair<int,int> xd = query(1,k,1,base,x,x);
            //cout << x << ' ' << (1<<k) << ' ' << xd.first << ' ' << xd.second << '\n';
        }
    }
    cin >> q;
    while(q--){
        cin >> a >> b;
        int odp=0;
        pair<int,int> range = {a,a};
        for (int k=K-1;k>=0;k--){
            pair<int,int> temp = query(1,k,1,base,range.first,range.second);
            if (!(temp.first <= b && b <= temp.second)){
                odp += (1<<k);
                range =temp;
            }
        }
        if (odp+1 == (1<<K)) cout << "-1\n";
        else cout << odp+1 << '\n';
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:87:27: warning: variable 'xd' set but not used [-Wunused-but-set-variable]
   87 |             pair<int,int> xd = query(1,k,1,base,x,x);
      |                           ^~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 43356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 43356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1269 ms 43528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1330 ms 43656 KB Output is correct
2 Correct 1493 ms 43580 KB Output is correct
3 Correct 1678 ms 43788 KB Output is correct
4 Correct 1123 ms 43524 KB Output is correct
5 Correct 1152 ms 43604 KB Output is correct
6 Correct 1150 ms 43612 KB Output is correct
7 Correct 1448 ms 43528 KB Output is correct
8 Correct 1332 ms 43788 KB Output is correct

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1643 ms 43668 KB Output is correct
2 Correct 1579 ms 43788 KB Output is correct
3 Correct 1515 ms 43884 KB Output is correct
4 Correct 1469 ms 43788 KB Output is correct
5 Correct 1318 ms 43524 KB Output is correct
6 Correct 1502 ms 44236 KB Output is correct
7 Correct 1375 ms 43524 KB Output is correct
8 Correct 70 ms 43528 KB Output is correct
9 Correct 91 ms 43604 KB Output is correct
10 Correct 1274 ms 43600 KB Output is correct
11 Correct 1494 ms 43824 KB Output is correct
12 Correct 1538 ms 43624 KB Output is correct
13 Correct 1506 ms 43528 KB Output is correct
14 Incorrect 68 ms 43356 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 43356 KB Output isn't correct
2 Halted 0 ms 0 KB -