답안 #1013856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013856	2024-07-04T06:57:18 Z	hengliao	Fire (BOI24_fire)	C++17	34 / 100	234 ms	101928 KB

Main

#include<bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

const ll mxN=2e5+5;
const ll LOG=21;
const ll inf=1e18;

ll pw[LOG];

struct seg{
    ll s, e;
    seg *up[LOG];

    bool operator< (const seg &tar) const{
        if(s!=tar.s){
            return s<tar.s;
        }
        return e<tar.e;
    }

    ll bs(ll tar){
        ll re=0;
        if(e>=tar){
            return 1;
        }
        seg *cur=this;
        for(ll i=LOG-1;i>=0;i--){
            if(cur->up[i]->e<tar){
                re+=pw[i];
                cur=cur->up[i];
            }
        }
        return re+2;
    }
};

ll n, m;
vector<seg> a;
vll con;

ll getidx(ll tar){
    return lower_bound(con.begin(), con.end(), tar)-con.begin();
}

void solve(){
	cin>>n>>m;
    //a.resize(n);
    vector<pll> tep(n);
    for(ll i=0;i<n;i++){
        cin>>tep[i].F>>tep[i].S;
    }
    for(ll i=0;i<n;i++){
        if(tep[i].F>tep[i].S){
            tep[i].S+=m;
        }
    }
    sort(tep.begin(), tep.end());
    //a.erase(unique(a.begin(), a.end()), a.end());
    pll pre={0, 0};
    for(ll i=0;i<n;i++){
        if(tep[i].F!=pre.F || tep[i].S!=pre.S){
            a.pb({tep[i].F, tep[i].S});
        }
    }
    n=a.size();
    for(ll i=0;i<n;i++){
        seg tep={a[i].s+m, a[i].e+m};
        tep.e=min(tep.e, 2*m);
        a.pb(tep);
    }
    for(auto &cur:a){
        con.pb(cur.s);
        con.pb(cur.e);
    }
    sort(con.begin(), con.end());
    con.erase(unique(con.begin(), con.end()), con.end());
    ll pt=0;
    seg *mx=new seg();
    mx->s=0;
    mx->e=0;
    vector<seg*> bst(con.size());
    for(ll i=0;i<con.size();i++){
        ll it=con[i];
        if(it<a[0].s) continue;
        while(pt<a.size() && a[pt].s<=it){
            if(a[pt].e>(mx->e)){
                mx=&a[pt];
            }
            pt++;
        }
        bst[i]=mx;
    }
    for(ll i=0;i<a.size();i++){
        ll id=getidx(a[i].e);
        a[i].up[0]=bst[id];
    }
    for(ll j=1;j<LOG;j++){
        for(ll i=0;i<a.size();i++){
            a[i].up[j]=a[i].up[j-1]->up[j-1];
        }
    }
    for(ll i=0;i<n;i++){
        if(a[i].up[LOG-1]->e<a[i].s+m){
            cout<<-1<<'\n';
            return;
        }
    }
    ll ans=inf;
    for(ll i=0;i<n;i++){
        ll re=a[i].bs(a[i].s+m);
        //cout<<a[i].s<<' '<<a[i].e<<' '<<re<<'\n';
        ans=min(ans, re);
    }
    cout<<ans<<'\n';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    pw[0]=1;
    for(ll i=1;i<LOG;i++){
        pw[i]=pw[i-1]*2;
    }

	solve();
	return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:91:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(ll i=0;i<con.size();i++){
      |                ~^~~~~~~~~~~
Main.cpp:94:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         while(pt<a.size() && a[pt].s<=it){
      |               ~~^~~~~~~~~
Main.cpp:102:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(ll i=0;i<a.size();i++){
      |                ~^~~~~~~~~
Main.cpp:107:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for(ll i=0;i<a.size();i++){
      |                    ~^~~~~~~~~

Subtask #1
0 / 14.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	456 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
0 / 17.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	456 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #3
0 / 9.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	456 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #4
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 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	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	1 ms	716 KB	Output is correct
15	Correct	5 ms	3596 KB	Output is correct
16	Correct	6 ms	3600 KB	Output is correct
17	Correct	5 ms	3600 KB	Output is correct
18	Correct	5 ms	3600 KB	Output is correct
19	Correct	6 ms	3724 KB	Output is correct
20	Correct	147 ms	98820 KB	Output is correct
21	Correct	209 ms	101720 KB	Output is correct
22	Correct	234 ms	101928 KB	Output is correct
23	Correct	195 ms	101256 KB	Output is correct
24	Correct	212 ms	101900 KB	Output is correct
25	Correct	228 ms	101264 KB	Output is correct
26	Correct	212 ms	101920 KB	Output is correct
27	Correct	202 ms	101724 KB	Output is correct
28	Correct	186 ms	101724 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	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	604 KB	Output is correct
9	Correct	0 ms	604 KB	Output is correct
10	Correct	0 ms	604 KB	Output is correct
11	Correct	0 ms	604 KB	Output is correct
12	Correct	5 ms	3600 KB	Output is correct
13	Correct	4 ms	3596 KB	Output is correct
14	Correct	4 ms	3668 KB	Output is correct
15	Correct	177 ms	98696 KB	Output is correct
16	Correct	199 ms	100960 KB	Output is correct
17	Correct	201 ms	101772 KB	Output is correct
18	Correct	196 ms	101720 KB	Output is correct
19	Correct	209 ms	101748 KB	Output is correct
20	Correct	202 ms	100956 KB	Output is correct

Subtask #6
0 / 26.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	456 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

답안 #1013856

Compilation message

Subtask #1 0 / 14.0

Subtask #2 0 / 17.0

Subtask #3 0 / 9.0

Subtask #4 13.0 / 13.0

Subtask #5 21.0 / 21.0

Subtask #6 0 / 26.0

Subtask #1
0 / 14.0

Subtask #2
0 / 17.0

Subtask #3
0 / 9.0

Subtask #4
13.0 / 13.0

Subtask #5
21.0 / 21.0

Subtask #6
0 / 26.0