oj.uz

Submission #1104545

# Submission time Handle Problem Language Result Execution time Memory
1104545 2024-10-24T02:58:15 Z 12345678 Fire (BOI24_fire) C++17
0 / 100
 2 ms 6736 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5, kx=18;

ll n, m, pa[nx][kx], sm[nx][kx], t, vl[nx][2], sh[nx][2], ans;
map<ll, ll> mp, rvmp;

struct segtree
{
    pair<ll, ll> d[16*nx];
    void update(int l, int r, int i, int idx, pair<ll, ll> vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=max(d[i], vl), void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }  
    pair<ll, ll> query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return {0, 0};
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++)
    {
        cin>>vl[i][0]>>vl[i][1];
        if (vl[i][1]<vl[i][0]) vl[i][1]+=m;
        sh[i][0]=vl[i][0]+m;
        sh[i][1]=vl[i][1]+m;
        mp[vl[i][0]]=mp[vl[i][1]]=mp[sh[i][0]]=mp[sh[i][1]]=0;
    }
    for (auto &[x, y]:mp) y=++t;
    for (auto [x, y]:mp) rvmp[y]=x;
    for (int i=1; i<=n ;i++) vl[i][0]=mp[vl[i][0]], vl[i][1]=mp[vl[i][1]], sh[i][0]=mp[sh[i][0]], sh[i][1]=mp[sh[i][1]];
    for (int i=1; i<=n; i++) s.update(1, 4*n, 1, vl[i][0], {vl[i][1], i}), s.update(1, 4*n, 1, sh[i][0], {sh[i][1], i});
    for (int i=1; i<=n; i++)
    {
        auto mx=s.query(1, 4*n, 1, vl[i][0], vl[i][1]);
        mx.first=rvmp[mx.first];
        auto tmp=rvmp[vl[i][1]];
        if (mx.first<=tmp) continue;
        pa[i][0]=mx.second;
        sm[i][0]=mx.first-tmp;
        //cout<<"pa "<<i<<' '<<pa[i][0]<<' '<<sm[i][0]<<'\n';
    }
    for (int j=1; j<kx; j++) for (int i=1; i<=n; i++) pa[i][j]=pa[pa[i][j-1]][j-1], sm[i][j]=sm[i][j-1]+sm[pa[i][j-1]][j-1];
    for (int i=1; i<=n; i++)
    {
        ll cur=rvmp[vl[i][1]]-rvmp[vl[i][0]], u=i, cnt=1;
        for (int j=kx-1; j>=0; j--) if (cur+sm[u][j]<m) cnt+=1<<j, cur+=sm[u][j], u=pa[u][j];
        //cout<<"cur "<<cur<<' '<<cnt<<'\n';
        if (cur+sm[u][0]<m||u==0) continue;
        ans=max(ans, cnt+1);
    }
    if (ans==0) cout<<-1;
    else cout<<ans;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 13.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Correct 2 ms 6580 KB Output is correct
4 Correct 1 ms 6480 KB Output is correct
5 Correct 1 ms 6480 KB Output is correct
6 Correct 1 ms 6648 KB Output is correct
7 Correct 1 ms 6480 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 2 ms 6736 KB Output is correct
10 Incorrect 2 ms 6736 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

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