제출 #1013733

#제출 시각아이디문제언어결과실행 시간메모리
1013733hengliaoFire (BOI24_fire)C++17
34 / 100
205 ms88896 KiB
#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); for(ll i=0;i<n;i++){ cin>>a[i].s>>a[i].e; } for(ll i=0;i<n;i++){ if(a[i].s>a[i].e){ a[i].e+=m; } } sort(a.begin(), a.end()); 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); 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; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void solve()':
Main.cpp:82: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]
   82 |     for(ll i=0;i<con.size();i++){
      |                ~^~~~~~~~~~~
Main.cpp:85: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]
   85 |         while(pt<a.size() && a[pt].s<=it){
      |               ~~^~~~~~~~~
Main.cpp:93: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]
   93 |     for(ll i=0;i<a.size();i++){
      |                ~^~~~~~~~~
Main.cpp:98: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]
   98 |         for(ll i=0;i<a.size();i++){
      |                    ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...