| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1093416 |
2024-09-26T19:19:19 Z |
Tymond |
Fire (BOI24_fire) |
C++17 |
|
1 ms |
468 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
struct Info{
ll ind, blokSz, blokMod, val;
Info(ll nind, ll nb, ll nm, ll nv){
ind = nind;
blokSz = nb;
blokMod = nm;
val = nv;
}
};
const int MAXN = 2e5 + 7;
int p[MAXN];
int e[MAXN];
int tp[MAXN];
int n, m;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
vector<pair<pii, int>> vec;
for(int i = 1; i <= n; i++){
cin >> p[i] >> e[i];
if(p[i] < e[i]){
tp[i] = 0;
vec.pb({{p[i], e[i]}, i});
}else{
tp[i] = 1;
if(e[i] != 0){
vec.pb({{0, e[i]}, i});
}
if(p[i] != m - 1){
vec.pb({{p[i], m - 1}, i});
}
}
}
sort(all(vec));
int ans = 0;
int k = 0;
set<pii> s;
int wsk = 0;
vi used;
while(k < m - 1){
while(wsk < sz(vec) && vec[wsk].fi.fi <= k){
s.insert({vec[wsk].fi.se, vec[wsk].se});
wsk++;
}
if(sz(s) == 0){
cout << -1 << '\n';
return 0;
}
if((*(--s.end())).fi <= k){
cout << -1 << '\n';
return 0;
}
ans++;
k = (*(--s.end())).fi;
used.pb((*(--s.end())).se);
s.erase(--s.end());
//cout << k << '\n';
}
if(ans == 1){
cout << ans << '\n';
return 0;
}
//cout << ans << '\n';
//for(auto ele : used){
// cout << ele << ' ';
//}
//cout << '\n';
for(int i = 1; i <= n; i++){
if(tp[i] == 0){
continue;
}
int len = sz(used);
if(used[0] == i && used.back() == i){
len--;
}else if(used[0] != i && used.back() != i){
len++;
}
//cout << i << ' ' << len << '\n';
if(p[used[1]] <= e[i]){
int l = 0;
int hi = sz(used) - 2;
int mid;
while(l < hi){
mid = (l + hi + 1) / 2;
if(p[used[mid + 1]] <= e[i]){
l = mid;
}else{
hi =mid - 1;
}
}
len -= (l + 1);
if(used.back() == i){
len++;
}
}
if(p[i] <= e[used[sz(used) - 2]]){
int l = 1;
int hi = sz(used) - 1;
int mid;
while(l < hi){
mid = (l + hi) / 2;
if(e[used[mid - 1]] >= p[i]){
hi = mid;
}else{
l = mid + 1;
}
}
//cout << l << '\n';
len -= (sz(used) - l);
if(used[0] == i){
len++;
}
}
ans = min(ans, len);
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
