Submission #1247970

#TimeUsernameProblemLanguageResultExecution timeMemory
1247970hainam2k9Fire (BOI24_fire)C++20
40 / 100
104 ms14996 KiB
#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],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;
      |                                             ^~
#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...