이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |