oj.uz

Submission #1033925

# Submission time Handle Problem Language Result Execution time Memory
1033925 2024-07-25T07:47:35 Z 정희우(#10973) Fire (BOI24_fire) C++17
34 / 100
 105 ms 45116 KB 
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
using lint = long long;
using intp = pair<int,int>;
using vint = vector<int>;

const int MAX_N=200010;
const int BN=20;

struct Obj
{
    lint s,e;
    bool operator < (const Obj &o) const
    {
        return (s==o.s) ? e>o.e : s<o.s;
    }
};

int n;
lint m;
Obj pos[MAX_N];
vector<Obj> v;
int ac[MAX_N<<1][BN];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i=0;i<n;i++)
    {
        cin >> pos[i].s >> pos[i].e;
        if(pos[i].s>pos[i].e)pos[i].e+=m;
    }
    sort(pos,pos+n);
    for(int i=0;i<n;i++)
        if(v.empty() || v.back().e<pos[i].e)v.push_back(pos[i]);
    n=v.size();
    for(int i=0;i<n;i++)
        v.push_back({v[i].s+m,v[i].e+m});
    fill(ac[n*2-1],ac[n*2-1]+BN,n*2-1);
    for(int i=n*2-2;i>=0;i--)
    {
        int p=lower_bound(v.begin(),v.end(),(Obj){v[i].e,0})-v.begin()-1;
        if(p==i)
        {
            cout << -1;
            return 0;
        }
        ac[i][0]=p;
        for(int j=1;j<BN;j++)
            ac[i][j]=ac[ac[i][j-1]][j-1];
    }
    int ans=n;
    for(int i=0;i<n;i++)
    {
        int p=i,c=1;
        for(int j=BN-1;j>=0;j--)
            if(ac[p][j]<n+i)
            {
                p=ac[p][j];
                c+=1<<j;
            }
        ans=min(ans,c);
    }
    cout << ans;
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 1504 KB Output is correct
16 Correct 2 ms 1504 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 2 ms 1704 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 19 ms 4188 KB Output is correct
21 Correct 47 ms 12092 KB Output is correct
22 Correct 45 ms 10700 KB Output is correct
23 Correct 95 ms 43960 KB Output is correct
24 Correct 84 ms 36524 KB Output is correct
25 Correct 39 ms 6736 KB Output is correct
26 Correct 68 ms 26252 KB Output is correct
27 Correct 100 ms 44904 KB Output is correct
28 Correct 44 ms 10200 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 476 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 4 ms 1500 KB Output is correct
13 Correct 3 ms 1504 KB Output is correct
14 Correct 2 ms 1500 KB Output is correct
15 Correct 21 ms 4244 KB Output is correct
16 Correct 103 ms 43952 KB Output is correct
17 Correct 99 ms 44976 KB Output is correct
18 Correct 94 ms 45116 KB Output is correct
19 Correct 105 ms 45104 KB Output is correct
20 Correct 94 ms 43952 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -