oj.uz

답안 #890183

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
890183 2023-12-20T16:18:59 Z ace5 Railway Trip 2 (JOI22_ho_t4) C++17
8 / 100
 290 ms 33236 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100001,maxlogn = 17;
const int sqr = 200;

int st[4][maxlogn][maxn];
int maxst[maxn];
int l[maxn];
int r[maxn];

int MIN1(int l,int r)
{
    int ts = maxst[r-l+1];
    return min(st[0][ts][l],st[0][ts][r-(1<<ts)+1]);
}
int MAX1(int l,int r)
{
    int ts = maxst[r-l+1];
    return max(st[1][ts][l],st[1][ts][r-(1<<ts)+1]);
}
int MINs(int l,int r)
{
    int ts = maxst[r-l+1];
    return min(st[2][ts][l],st[2][ts][r-(1<<ts)+1]);
}
int MAXs(int l,int r)
{
    int ts = maxst[r-l+1];
    return max(st[3][ts][l],st[3][ts][r-(1<<ts)+1]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    int m;
    cin >> m;
    vector<int> tl(n),tr(n);
    for(int i = 0;i < n;++i)
    {
        tl[i] = i;
        tr[i] = i;
    }
    for(int i = 0;i < m;++i)
    {
        int lx,rx;
        cin >> lx >> rx;
        lx--;
        rx--;
        if(lx > rx)
        {
            tl[lx] = min(tl[lx],rx);
        }
        else
        {
            tr[lx] = max(tr[lx],rx);
        }
    }
    multiset<int> cc;
    for(int i = n-1;i >= 0;--i)
    {
        if(i+k < n)
        {
            cc.erase(cc.find(tl[i+k]));
        }
       // cout << tl[i] << ' ';
        cc.insert(tl[i]);
        l[i] = *cc.begin();
       // cout << l[i] << ' ';
    }
   // cout << "\n";
    cc.clear();
    for(int i = 0;i < n;++i)
    {
        if(i >= k)
        {
            cc.erase(cc.find(-tr[i-k]));
        }
        cc.insert(-tr[i]);
        r[i] = -(*cc.begin());
       // cout << r[i] << ' ';
    }
   // cout << "\n";
    int tst = 0;
    for(int j = 1;j < maxn;++j)
    {
        maxst[j] = tst;
        if((1<<(tst+1)) <= j+1)
            tst++;
    }
    for(int i = 0;i < maxlogn;++i)
    {
        for(int j = 0;j < n-(1<<i)+1;++j)
        {
            if(i == 0)
                st[0][i][j] = l[j];
            else
                st[0][i][j] = min(st[0][i-1][j],st[0][i-1][j+(1<<(i-1))]);
        }
    }
    for(int i = 0;i < maxlogn;++i)
    {
        for(int j = 0;j < n-(1<<i)+1;++j)
        {
            if(i == 0)
                st[1][i][j] = r[j];
            else
                st[1][i][j] = max(st[1][i-1][j],st[1][i-1][j+(1<<(i-1))]);
        }
    }
    for(int i = 0;i < sqr-1;++i)
    {
        for(int j = 0;j < n;++j)
        {
            int nl = MIN1(l[j],r[j]);
            int nr = MAX1(l[j],r[j]);
            l[j] = nl;
            r[j] = nr;
        }
    }
    for(int i = 0;i < maxlogn;++i)
    {
        for(int j = 0;j < n-(1<<i)+1;++j)
        {
            if(i == 0)
                st[2][i][j] = l[j];
            else
                st[2][i][j] = min(st[2][i-1][j],st[2][i-1][j+(1<<(i-1))]);
        }
    }
    for(int i = 0;i < maxlogn;++i)
    {
        for(int j = 0;j < n-(1<<i)+1;++j)
        {
            if(i == 0)
                st[3][i][j] = r[j];
            else
                st[3][i][j] = max(st[3][i-1][j],st[1][i-1][j+(1<<(i-1))]);
        }
    }
  //  cout << MIN1(1,1);
    int q;
    cin >> q;
    while(q--)
    {
        int s,t;
        cin >> s >> t;
        s--;
        t--;
        int ls = s,rs = s;
        int ans = 0;
        int y = 0;
        for(int j = 0;j < sqr;++j)
        {
            int nls = MINs(ls,rs);
            int nrs = MAXs(ls,rs);
            if(nls > t || nrs < t)
            {
                ls = nls;
                rs = nrs;
                ans += sqr;
            }
            else
            {
                y=  1;
                break;
            }
        }
        for(int j = 0;j < sqr;++j)
        {
            int nls = MIN1(ls,rs);
            int nrs = MAX1(ls,rs);
            if(nls > t || nrs < t)
            {
                ls = nls;
                rs = nrs;
                ans ++;
            }
            else
            {
                ans ++;
                y = 1;
                break;
            }
        }
        if(!y)
            cout << -1 << "\n";
        else
            cout << ans << "\n";
    }
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 3 ms 22876 KB Output is correct
3 Correct 3 ms 22876 KB Output is correct
4 Correct 4 ms 22876 KB Output is correct
5 Correct 3 ms 22876 KB Output is correct
6 Correct 3 ms 22876 KB Output is correct
7 Correct 3 ms 22876 KB Output is correct
8 Correct 5 ms 22876 KB Output is correct
9 Correct 3 ms 22876 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 3 ms 22876 KB Output is correct
12 Correct 3 ms 23048 KB Output is correct
13 Incorrect 7 ms 24924 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 29680 KB Output is correct
2 Incorrect 248 ms 28572 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 3 ms 22876 KB Output is correct
3 Correct 3 ms 22876 KB Output is correct
4 Correct 4 ms 22876 KB Output is correct
5 Correct 3 ms 22876 KB Output is correct
6 Correct 3 ms 22876 KB Output is correct
7 Correct 3 ms 22876 KB Output is correct
8 Correct 5 ms 22876 KB Output is correct
9 Correct 3 ms 22876 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 3 ms 22876 KB Output is correct
12 Correct 3 ms 23048 KB Output is correct
13 Incorrect 7 ms 24924 KB Output isn't correct
14 Halted 0 ms 0 KB -