Submission #1247976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247976		hainam2k9	Fire (BOI24_fire)	C++20	100 / 100	107 ms	28172 KiB

Main

#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 2e5+5;
const string NAME = "test";
int n,m,nxt[20][MAXN<<2],rs=1e9;
pair<int,int> p[MAXN];
void compress(){
    vector<int> v;
    for(int i = 1; i<=n; ++i)
        v.pb(p[i].fi), v.pb(p[i].se);
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());
    for(int i = 1; i<=n; ++i)
        p[i].fi=lb(v.begin(),v.end(),p[i].fi)-v.begin()+1,
        p[i].se=lb(v.begin(),v.end(),p[i].se)-v.begin()+1;
    m=sz(v);
}
int query(int l, int r){
    int rs=0;
    for(int i = __lg(m); i>=0; --i)
        if(nxt[i][l]>0&&nxt[i][l]<r) rs|=1<<i, l=nxt[i][l];
    if(nxt[0][l]==0||nxt[0][l]<r) rs=1e9;
    return rs+1;
}
int main()
{
    tt;
    if(fopen((NAME + ".INP").c_str(), "r")) fo;
    cin >> n >> m;
    for(int i = 1; i<=n; ++i)
        cin >> p[i].fi >> p[i].se;
    compress();
    for(int i = 1; i<=n; ++i){
        if(p[i].fi<p[i].se) nxt[0][p[i].fi]=max(nxt[0][p[i].fi],p[i].se);
        else nxt[0][p[i].fi]=m+1;
    }
    for(int i = 1; i<=m; ++i)
        nxt[0][i]=max(nxt[0][i],nxt[0][i-1]);
    for(int i = 1; i<=__lg(m); ++i)
        for(int j = 1; j<=m; ++j)
            if(nxt[i-1][nxt[i-1][j]]>nxt[i-1][j]) nxt[i][j]=nxt[i-1][nxt[i-1][j]];
    for(int i = 1; i<=n; ++i){
        if(p[i].fi<p[i].se) continue;
        rs=min(rs,query(p[i].se,p[i].fi)+1);
    }
    if(rs>n) cout << -1;
    else cout << rs;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:3:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:45:45: note: in expansion of macro 'fo'
   45 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~
Main.cpp:3:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:45:45: note: in expansion of macro 'fo'
   45 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 13 / 13
• Subtask 5: 21 / 21
• Subtask 6: 26 / 26