답안 #1013859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013859	2024-07-04T06:59:08 Z	hengliao	Fire (BOI24_fire)	C++17	34 / 100	237 ms	101956 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){
            assert(0);
            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:97: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]
   97 |         while(pt<a.size() && a[pt].s<=it){
      |               ~~^~~~~~~~~
Main.cpp:105: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]
  105 |     for(ll i=0;i<a.size();i++){
      |                ~^~~~~~~~~
Main.cpp:110: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]
  110 |         for(ll i=0;i<a.size();i++){
      |                    ~^~~~~~~~~

Subtask #1
0 / 14.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 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	348 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	348 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	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	600 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	860 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	0 ms	604 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	5 ms	3600 KB	Output is correct
16	Correct	5 ms	3600 KB	Output is correct
17	Correct	5 ms	3600 KB	Output is correct
18	Correct	4 ms	3600 KB	Output is correct
19	Correct	4 ms	3600 KB	Output is correct
20	Correct	165 ms	98668 KB	Output is correct
21	Correct	209 ms	101936 KB	Output is correct
22	Correct	195 ms	101764 KB	Output is correct
23	Correct	190 ms	100988 KB	Output is correct
24	Correct	213 ms	101956 KB	Output is correct
25	Correct	237 ms	101212 KB	Output is correct
26	Correct	204 ms	101788 KB	Output is correct
27	Correct	191 ms	101916 KB	Output is correct
28	Correct	187 ms	101720 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 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	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 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	3636 KB	Output is correct
13	Correct	4 ms	3596 KB	Output is correct
14	Correct	4 ms	3596 KB	Output is correct
15	Correct	153 ms	98896 KB	Output is correct
16	Correct	184 ms	100976 KB	Output is correct
17	Correct	209 ms	101840 KB	Output is correct
18	Correct	202 ms	101884 KB	Output is correct
19	Correct	215 ms	101496 KB	Output is correct
20	Correct	175 ms	100864 KB	Output is correct

Subtask #6
0 / 26.0

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

답안 #1013859

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